/
index.ts
44 lines (41 loc) · 1003 Bytes
/
index.ts
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
export default function combinationSum2(
candidates: number[],
target: number,
): number[][] {
candidates.sort((a, b) => -b + a);
const ans: number[][] = [];
dfs(candidates, target, [], function (path: number[]) {
return ans.push(path);
});
return ans;
}
function dfs(
candidates: number[],
target: number,
path: number[],
output: (path: number[]) => void,
) {
if (target === 0) {
output(path);
return;
}
for (const [index, can] of candidates.entries()) {
if (target >= can) {
if (
!(
candidates[index - 1] &&
candidates[index] === candidates[index - 1]
)
) {
dfs(
candidates.slice(index + 1),
target - can,
[...path, can],
output,
);
}
} else {
return;
}
}
}