Combination Sum 组合数求和-Leetcode

老白

发布于 2018-03-19 15:55:57

1.1K0

发布于 2018-03-19 15:55:57

原题：

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]

题意是找到所有加起来和为target值的组合，候选数可以重复使用。这明显是一道利用回溯的题目，可以想象成深度搜索。

以题目给出的【2，3，6，7】为例。一棵树根节点有四个子节点（2，3，6，7）。每个子节点下又有不小于本子节点的所有子节点。比如子节点2下面仍然有（2，3，6，7）四个子节点，子节点3下面有（3，6，7）三个子节点。我们就在这样一棵树上进行深搜，返回的条件是经过的节点的和为target。停止的条件是返回到根节点且无下一个子节点可用。

public class Solution {
    public List<List<Integer>> combinationSum(int[] candidates, int target) {
        Arrays.sort(candidates);
        solve(candidates,0,target,new LinkedList<Integer>());
        return ans;
    }
    private List<List<Integer>> ans=new LinkedList<>();
    private  void solve(int[] candidates,int start,int target,LinkedList<Integer> current){
        if (target==0){
            ans.add(copy(current));
            return;
        }
        if (target<candidates[start]){
            return;
        }
        else {
            for (int iterator=start;iterator<candidates.length;iterator++){
                if (candidates[iterator]>target){
                    break;
                }
                current.add(candidates[iterator]);
                solve(candidates, iterator, target - candidates[iterator], current);
                current.pollLast();
            }
            return;
        }
    }
    private LinkedList<Integer> copy(LinkedList<Integer> source){
        LinkedList<Integer> dest=new LinkedList<>();
        for (int i:source){
            dest.add(i);
        }
        return dest;
    }
}

另一个效率更高的算法，逆向思维。

public class Solution {
    public List<List<Integer>> combinationSum(int[] candidates, int target) {
        return combinationSum(candidates, target, 0);
    }

    public List<List<Integer>> combinationSum(int[] candidates, int target, int start) {

        List<List<Integer>> res = new ArrayList<List<Integer>>();
        Arrays.sort(candidates);
        for (int i = start; i < candidates.length; i++) {
            if (candidates[i] <target) {
                for (List<Integer> ar : combinationSum(candidates, target - candidates[i], i)) {
                    ar.add(0, candidates[i]);
                    res.add(ar);
                }
            } else if (candidates[i] == target) {
                List<Integer> lst = new ArrayList<>();
                lst.add(candidates[i]);
                res.add(lst);
            } else
                break;
        }
        return res;
    }
}

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

原始发表：2015-09-20 ，如有侵权请联系 cloudcommunity@tencent.com 删除

combinations