DAY 30
0

## #39 Combination Sum

#### 題目敘述：

``````Given a set of candidate numbers (C) (without duplicates) and a target number (T), find all unique combinations in C where the candidate numbers sums to T.

The same repeated number may be chosen from C unlimited number of times.

Note:
All numbers (including target) will be positive integers.
The solution set must not contain duplicate combinations.

For example, given candidate set [2, 3, 6, 7] and target 7,
A solution set is:

[
[7],
[2, 2, 3]
]
``````

#### 題目解答：

``````/**
* @param {number[]} candidates
* @param {number} target
* @return {number[][]}
*/
const dfs = (start, target, candidates, sum, curArr, result) => {
if(sum === target) {
result.push(curArr.concat());
}

for(let i = start; i < candidates.length; i++) {
if(sum + candidates[i] <= target) {
curArr.push(candidates[i]);
dfs(i, target, candidates, sum + candidates[i], curArr, result);
curArr.pop();
}
}
};

const combinationSum = (candidates, target) => {
let result = [];
candidates.sort((a, b) => {
return a > b ? 1 : -1;
})

dfs(0, target, candidates, 0, [], result);

return result;
};
``````

#### 解題步驟：

• 步驟 1.
我們先幫 `candidates` 進行排序，是方便後面用加的方式可以少遞迴一些，
然後我們把參數傳進去 `dfs()`
``````const combinationSum = (candidates, target) => {
let result = [];
candidates.sort((a, b) => {
return a > b ? 1 : -1;
})

dfs(0, target, candidates, 0, [], result);

return result;
};
``````
• 步驟 2.
這裡是主要遞迴的部分，
首先，只有 `sum === target` 時我們才要把這個組合放進答案 `result` 裡，

接著，一樣一次放一個數字進去加看看，要注意的是，傳給 `dfs` 的第一個參數 `i` 不需要 `+1`，因為 `i` 是可以重複使用的，如果說不能重使用的話，那就不能讓 `i` 在下一次遞迴時還跟這次一樣了！
然後跑完一次遞迴要 `pop` 掉一個空位給下一個數字進來家看看，完成！

``````const dfs = (start, target, candidates, sum, curArr, result) => {
if(sum === target) {
result.push(curArr.concat());
}

for(let i = start; i < candidates.length; i++) {
if(sum + candidates[i] <= target) {
curArr.push(candidates[i]);
dfs(i, target, candidates, sum + candidates[i], curArr, result);
curArr.pop();
}
}
};
``````