官网模板建站塔山双喜_义乌高端网站设计品牌_代运营靠谱吗_网站多久被百度收录

 题目：

---

方法一：

解析： 

---

 

代码： 

private List<List<Integer>> ret;private List<Integer> path;private int aim; public List<List<Integer>> combinationSum(int[] candidates, int target) {aim = target;ret = new ArrayList<>();path = new ArrayList<>();dfs(candidates,0,0);return ret;}private void dfs(int[] candidates,int pos, int sum){if(sum == aim){ret.add(new ArrayList<>(path));return;} if(aim < sum || pos == candidates.length) return;//剪枝二for(int i = pos; i < candidates.length; i++){path.add(candidates[i]);dfs(candidates,i, sum + candidates[i]);//剪枝一：从i开始往后选择path.remove(path.size()-1);}}

---

方法二： 

 

---

代码： 

 /**方法二：枚举元素个数 */ private List<List<Integer>> ret;private List<Integer> path;private int aim; public List<List<Integer>> combinationSum(int[] candidates, int target) {aim = target;ret = new ArrayList<>();path = new ArrayList<>();dfs(candidates,0,0);return ret;}private void dfs(int[] candidates,int pos, int sum){if(sum == aim){ret.add(new ArrayList<>(path));return;} if(aim < sum || pos == candidates.length) return;//剪枝二//k来枚举个数, candidates出现多少次for(int k = 0; k*candidates[pos] + sum <= aim; k++){if(k != 0) path.add(candidates[pos]);   dfs(candidates,pos+1,sum + k*candidates[pos]);}//回溯for(int k = 1; k*candidates[pos] + sum <= aim; k++)path.remove(path.size()-1);}