leecode-39. Combination Sum

1、问题描述：

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]

]

2、边界条件：无
3、思路：先取一个数，然后与target比较；==则存贮，！=则继续从所有数里面选择。
　　从Level-N里面选择一个数，与目标比较，符合则存贮；不符合则再从所有数里面挨个取，从而化为同样的Level-N问题
    形成递归。base case：1）与目标匹配；2）target - nums[i]<0,再减下去也是负数，这依赖于题目给的 全正数positive integers 条件
4、实现代码：

class Solution {

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

        List<List<Integer>> results = new ArrayList<>();

        //Arrays.sort(candidates);

        combinationSum(results, new ArrayList<Integer>(), candidates, target);

        return results;

    }

    public void combinationSum(List<List<Integer>> results, List<Integer> cur, int[] candidates, int target) {

        if (0 == target) {
　　　　　　　/**

            Collections.sort(cur);//这里排序会把原列表改变，所以上层在恢复现场时出错。

            if (!results.contains(cur)) {//去重

                results.add(new ArrayList<Integer>(cur));

            }
　　　　　　　**/

　　　　　　　　ArrayList<Integer> result = new ArrayList<Integer>(cur);//先生成新的cur，然后进行排序
　　　　　　　　Collections.sort(result); //
　　　　　　　　if (!results.contains(result)) {
　　　　　　　　　　results.add(result);
　　　　　　　　　　　　　　　return;

        }

        if (0 > target) {

            return;

        }

        for (int i = 0; i < candidates.length; i++) {

            cur.add(candidates[i]);

            combinationSum(results, cur, candidates, target - candidates[i]);

            cur.remove(cur.size() - 1);

        }

    }

}

5、时间复杂度：说不好；空间复杂度：

6、题外知识：Arraylist排序：Collections静态排序API，Collections的排序都是稳定的。Collections.sort(List<T> list)、和Collections.sort(List<T> list，Comparator<？super T> c);使用的排序是稳定的，主要是对list排序。

链接：http://blog.csdn.net/tuke_tuke/article/details/51100219 和 http://www.importnew.com/17211.html  
7、优化解法

class Solution {

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

        List<List<Integer>> results = new ArrayList<>();

        Arrays.sort(candidates);//排序是为了使得答案有序；如果有重复数字的情况下，可以方便去重。

        combinationSum(results, new ArrayList<Integer>(), candidates, target, 0);

        return results;

    }

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

        if (0 == target) {

            results.add(new ArrayList<Integer>(cur));

            return;

        }

        if (0 > target) {

            return;

        }

        for (int i = start; i < candidates.length; i++) { ///从start开始是因为前面的数字已经遍历过自己和后面的数字。

            cur.add(candidates[i]);

            combinationSum(results, cur, candidates, target - candidates[i], i);// not i + 1 because we can reuse same elements

            cur.remove(cur.size() - 1);

        }

    }

}

巴特西

leecode-39. Combination Sum

最新文章

热门文章