[leedcode 39] Combination Sum
Given a set of candidate numbers (C) and a target number (T), find all unique combinations inCwhere the candidate numbers sums toT.
Thesamerepeated number may be chosen fromCunlimited number of times.
Note:
For example, given candidate set2,3,6,7
and target7
,
A solution set is:[7]
[2, 2, 3]
public class Solution { List<Integer> seq; List<List<Integer>> res; public List<List<Integer>> combinationSum(int[] candidates, int target) { //类似全排列的变形,首先找到全排列,for循环加递归,终止条件是如果sum>target直接返回,如果sum=target则保存结果 //注意for循环的开始条件,以及递归的变量,本题允许每个数使用多次。level代表递归开始的candidates下标 //非常注意::在res中填值时,要重新new一个Integer,不能使用之前的,因为再操作seq会改变已经保存的值! Arrays.sort(candidates); seq=new ArrayList<Integer>(); res=new ArrayList<List<Integer>>(); find(candidates,target,0,0); return res; } public void find(int[] candidates,int target,int sum,int level){ if(sum==target){ res.add(new ArrayList<Integer>(seq)); return; } if(sum>target){ return; } for(int i=level;i<candidates.length;i++){ seq.add(candidates[i]); sum+=candidates[i]; find(candidates,target,sum,i); seq.remove(seq.size()-1);// sum-=candidates[i]; } } }优质内容筛选与推荐>>