39. Combination Sum (not use befroe, so int I = start, dfs(i) -> is i !!



time: O(2^n), candidate choose or not choose, n times
space: O(target)
class Solution {
public List<List<Integer>> combinationSum(int[] candidates, int target) {
List<List<Integer>> res = new ArrayList<>();
helper(res, new ArrayList<>(), candidates, target, 0);
return res;
}
private void helper(List<List<Integer>> res, List<Integer> list, int[] candidates, int target, int start) {
if (target < 0) {
return;
} else if (target == 0) {
res.add(new ArrayList<>(list));
} else {
for (int i = start; i < candidates.length; i++) {
list.add(candidates[i]);
helper(res, list, candidates, target - candidates[i], i); // pass i, why i = start => for seq search
list.remove(list.size()-1);
}
}
}
}
/*
7 - any of [],
7 = [2,3,6,7]
7 - 2 = 5
5 - 2 = 3
3 - 2 => no, 3 - 3 ok! backtrack
*/
why we cant just use for (i = 0..., because it should pass "the current index
and pass i, means we can reuse the same number
backtracking, we always have a tree (ex: [2, 3, 6, 7]), then cut and find the ans.
[2, 3, 6, 7]


class Solution {
public List<List<Integer>> combinationSum(int[] candidates, int target) {
List<List<Integer>> result = new ArrayList<>();
dfs(result, candidates, target, new ArrayList<>(), 0);
return result;
}
private void dfs(List<List<Integer>> result, int[] candidates, int target, List<Integer> list, int start) {
if (target < 0) {
return;
}
if (target == 0) {
result.add(new ArrayList<>(list));
return;
}
// if every time from i = 0, will generate like [2,2,3] [2,3,2], [3,2,2]
// just use order seq to pass the i index
for (int i = start; i < candidates.length; i++) {
list.add(candidates[i]);
dfs(result, candidates, target - candidates[i], list, i);
list.remove(list.size()-1);
}
}
}
想要避免這種狀況, 記得 use i = start, 並且傳入 i, 這樣可以保證傳入 i 的順序是對的, 就不會有重複問題
因為可以保證 2 在前面
會持續先用 2 來 try, 直到不行再開始退回 (所以也是為什麼 < target 要 return), 像這個最左邊的例子
當然 target == 0 時就會紀錄下來結果
2都 try 過多次後, 到最左邊的 -1 了, 退回, 才會開始用 3 來 try (所以分支就從-3 開始用了, -2 就不會在用了
所以這樣就能保證都先用 2 在用 3... 所以可以得到 [2,2,3]

如果用 i = 0
結果 [2,2,3] [2,3,2], [3,2,2] => 如果用 i = 0, 會
就是每次固定都用 4個分支去 try

5 . 4 1 . 0 4
-2 . -3 -2
3 2 x x 2 => -2 => [2,3,2] 2 => -2 => [3,2,2]
.-2 => [2,2,3]
這樣得到就是會其實有重複
Last updated
Was this helpful?