首页 > 代码库 > Leetcode: Combination Sum
Leetcode: Combination Sum
Given a set of candidate numbers (C) 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.Elements in a combination (a1, a2, … , ak) must be in non-descending order. (ie, a1 ≤ a2 ≤ … ≤ ak).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]
典型的recursion方法,找符合要求的path,存入result的ArrayList中。所以方法还是建立一个ArrayList<ArrayList<Integer>> result, 建立一个ArrayList<Integer> path,用recursion当找到符合条件的path时,存入result中。
我在做这道题时遇到了一个问题:添加 path 进入 result 中时,需要这样res.add(new ArrayList<Integer>(path)); 如果直接res.add(path); 会出错
比如我遇到的错误是:Input:[1], 1 Output:[[]] Expected:[[1]],没能够把path: [1] 添加到res里面去,没有成功。(具体我现在也不知道为什么)
1 public class Solution { 2 public ArrayList<ArrayList<Integer>> combinationSum(int[] candidates, int target) { 3 ArrayList<ArrayList<Integer>> res = new ArrayList<ArrayList<Integer>>(); 4 ArrayList<Integer> path = new ArrayList<Integer>(); 5 java.util.Arrays.sort(candidates); 6 findpaths(res, path, candidates, target); 7 return res; 8 } 9 10 public void findpaths(ArrayList<ArrayList<Integer>> res, ArrayList<Integer> path, int[] candidates, int remain) {11 if (remain == 0) {12 res.add(new ArrayList<Integer>(path));13 return;14 }15 if (remain < 0) {16 return;17 }18 for (int c : candidates) {19 if (path.size() != 0 && c < path.get(path.size() - 1)) continue;20 path.add(c);21 remain = remain - c;22 findpaths(res, path, candidates, remain);23 remain = remain + c;24 path.remove(path.size() - 1);25 }26 }27 }
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。