题目来源

力扣每日一题；题序：39

我的题解

方法一 回溯

以每一个位置开始深搜，直到target等于0或者小于0或者遍历完结束。
关键在于：注意去重 巧妙方法：传入一个index，是上一次遍历元素的位置，控制其不再去遍历前面的元素

时间复杂度：O($n\ast 2^n$)。n 个位置每次考虑选或者不选，如果符合条件，就加入答案的时间代价。但是实际运行的时候，因为不可能所有的解都满足条件，递归的时候还会用 target−candidates[idx]≥0进行剪枝，所以实际运行情况是远远小于这个时间复杂度的。
空间复杂度：O(n)

java">class Solution {List<List<Integer>> res;public List<List<Integer>> combinationSum(int[] candidates, int target) {res=new ArrayList<>();List<Integer> path=new ArrayList<>();for(int i=0;i<candidates.length;i++){path.add(candidates[i]);dfs(candidates,target-candidates[i],i,path);path.remove(path.size()-1);}return res;}public void dfs(int[] candidates,int target,int index,List<Integer> path){if(target==0)res.add(new ArrayList<>(path));//后一个条件的前提是candidates数组是升序的，这里是看了官方的题解，感觉默认是有序的if(target<0||target-candidates[index]<0)return ;for(int next=index;next<candidates.length;next++){path.add(candidates[next]);dfs(candidates,target-candidates[next],next,path);path.remove(path.size()-1);}}
}

有任何问题，欢迎评论区交流，欢迎评论区提供其它解题思路（代码），也可以点个赞支持一下作者哈😄~