[LeetCode] 39.Combination Sum

【原题】 Given a set of candidate numbers (C) (without duplicates) 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:

代码语言：javascript复制

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

For example, given candidate set [2, 3, 6, 7] and target 7, A solution set is:

代码语言：javascript复制

[
  [7],
  [2, 2, 3]
]

【解释】 给定一个集合（无重复元素），和一个目标值target，要求候选集合中的元素可能的和为target的所有集合。 【思路】 很典型的回溯法

代码语言：javascript复制

public class Solution {
    public void combinationSumCore(List<List<Integer>> results, List<Integer> result,int[] candidates,int index,int target,int sum){
        if(sum==target) {//得到集合加入results中并返回
            results.add(new ArrayList<Integer>(result));
            return;
        }
        if(sum>target) return;
        for(int i=index;i<candidates.length;i  ){
            result.add(candidates[i]);
            sum =candidates[i];
            combinationSumCore(results, result,candidates,i,target,sum);//由于这里候选集合的元素可以重复使用，所以从当前元素开始递归，在Combination SumII和III中，是从i 1开始的
            sum-=candidates[i];
            result.remove(result.size()-1);//回溯
        }
    }
    public List<List<Integer>> combinationSum(int[] candidates, int target) {
        List<List<Integer>> results=new ArrayList<List<Integer>>();
        List<Integer> result=new ArrayList<>();
        combinationSumCore(results,result,candidates,0,target,0);
        return results;
    }

}

combinations numbers set target unique

0 人点赞