Open Tcdian opened 3 years ago
/**
* @param {number[]} candidates
* @param {number} target
* @return {number[][]}
*/
var combinationSum2 = function(candidates, target) {
candidates.sort((a, b) => a - b);
const cache = new Set();
const reuslt = [];
const part = [];
backtracking(0);
return reuslt;
function backtracking(index) {
const sum = part.reduce((prev, current) => prev + current, 0);
if (sum >= target) {
if (sum === target) {
if (!cache.has(part.join(','))) {
cache.add(part.join(','));
reuslt.push([...part]);
}
}
return;
}
for (let i = index; i < candidates.length; i++) {
part.push(candidates[i]);
backtracking(i + 1);
part.pop();
}
}
};
function combinationSum2(candidates: number[], target: number): number[][] {
candidates.sort((a, b) => a - b);
const cache: Set<string> = new Set();
const reuslt: number[][] = [];
const part: number[] = [];
backtracking(0);
return reuslt;
function backtracking(index: number) {
const sum = part.reduce((prev, current) => prev + current, 0);
if (sum >= target) {
if (sum === target) {
if (!cache.has(part.join(','))) {
cache.add(part.join(','));
reuslt.push([...part]);
}
}
return;
}
for (let i = index; i < candidates.length; i++) {
part.push(candidates[i]);
backtracking(i + 1);
part.pop();
}
}
};
40. Combination Sum II
给定一个数组
candidates
和一个目标数target
,找出candidates
中所有可以使数字和为target
的组合。candidates
中的每个数字在每个组合中只能使用一次。Note
Example 1
Example 2