力扣hot100 组合总和 回溯 剪枝 组合

Problem: 39. 组合总和

思路

复杂度

时间复杂度: $O(n)$

空间复杂度: $O(n)$

💖 Code

class Solution{List<List<Integer>> res = new ArrayList<>();int x;// 全局targetint[] c;// 全局 candidatespublic List<List<Integer>> combinationSum(int[] candidates, int target){if (candidates == null || candidates.length == 0)return new ArrayList<>();x = target;c = candidates;dfs(0, 0, new ArrayList<Integer>());return res;}/*** @param sum  当前已选数的和* @param idx  当前选到的数的下标，下标 < idx 的数都不能选，防止重复* @param list 当前已选数列表*/private void dfs(int sum, int idx, ArrayList<Integer> list){if (sum >= x)// >= x 就返回{if (sum == x)// 只有 == x 时，才加入答案集合res.add(new ArrayList<>(list));return;}//从idx开始，idx前面的数选几个已经定了for (int i = idx; i < c.length; i++){list.add(c[i]);dfs(sum + c[i], i, list);list.remove(list.size() - 1);}}
}