LeetCode-39. Combination Sum

发布时间：2020-12-14 04:41:00 所属栏目：大数据来源：网络整理

导读：Given a?set?of candidate numbers ( candidates )?(without duplicates)?and a target number ( target ),find all unique combinations in? candidates ?where the candidate numbers sums to? target . The?same?repeated number may be chosen from? can

Given a?set?of candidate numbers (candidates)?(without duplicates)?and a target number (target),find all unique combinations in?candidates?where the candidate numbers sums to?target.

The?same?repeated number may be chosen from?candidates?unlimited number of times.

Note:

All numbers (including?target) will be positive integers.
The solution set must not contain duplicate combinations.

Example 1:

Input: candidates = target =,A solution set is:
[
  [7],[2,2,3]
]
[2,3,6,7],7

Example 2:

Input: candidates = [2,5]target = 8,A solution set is:
[
? [2,2],? [2,3],? [3,5]
],

先排序，然后搜索

    public List<List<Integer>> combinationSum(int[] candidates,int target) {
        List<List<Integer>> res = new ArrayList<List<Integer>>();
        List<Integer> curL = new ArrayList<Integer>();
        Arrays.sort(candidates);
        help(res,curL,candidates,target,0);
        return res;
    }
    private void help(List<List<Integer>> re,List<Integer> cur,int[] arr,int target,int value,int index){
        if(value==0){
            List<Integer> l=new ArrayList<>(cur);
            re.add(l);
            return;
        }
        else if(value>0){
            for(int i=index;i<arr.length&&arr[i]<=value;i++){
                cur.add(arr[i]);
                help(re,cur,arr,value-arr[i],i);
                cur.remove(cur.size()-1);
            }
        }
    }

（编辑：李大同）

【声明】本站内容均来自网络，其相关言论仅代表作者个人观点，不代表本站立场。若无意侵犯到您的权利，请及时与联系站长删除相关内容!