[LeetCode] 39.Combination Sum

用户1148830

发布于 2018-01-03 17:44:31

5660

【原题】 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:

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:

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

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

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;
    }

}

本文参与腾讯云自媒体同步曝光计划，分享自作者个人站点/博客。

原始发表：2017年06月26日，如有侵权请联系 cloudcommunity@tencent.com 删除

combinations