39. Combination Sum

题目：

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]

链接： http://leetcode.com/problems/combination-sum/

题解：

还是一道DFS + Backtracking题。这次是考察重复元素如何处理。依然使用回溯的template。

Time Complexity - O()， Space Complexity - O()

public class Solution {

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

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

        if(candidates == null || candidates.length == 0)

            return res;

        Arrays.sort(candidates);

        ArrayList<Integer> list = new ArrayList<>();

        dfs(res, list, candidates, target, 0);

        return res;

    }

    private void dfs(List<List<Integer>> res, ArrayList<Integer> list, int[] candidates, int target, int pos) {

        if(target < 0)

            return;

        if(target == 0) {

            res.add(new ArrayList<Integer>(list));

            return;

        }

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

            if(candidates[i] > target)

                return;

            if(i > 0 && candidates[i] == candidates[i - 1])

                continue;

            list.add(candidates[i]);

            dfs(res, list, candidates, target - candidates[i], i);

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

        }

    }

}

二刷：

典型的的dfs + backtracking, 一刷到现在有很长时间了,重新做到这题, 才会补充思考以前的不足. 这遍在想能不能用其他的方法, 比如dp或者是类似双指针之类的, 不过可惜最后还是选了这个熟悉的方法.

这里我们主要要注意的是用来回溯的helper方法如何设计, 在我用的方法里, 需要传入已有的变量有

List<List<Integer>> res，这个是我们的结果变量，只有找到满足条件的combination组合之后才会用到
List<Integer> combination，这个是我们用来进行回溯用到的主buffer，根据dfs的深度增加或者减少元素
int[] candidates，这个是题目给定的数组，我们先对其进行sort，然后从小到大遍历来选择合适的元素。这里由于可以不限量选取元素，所以假如candidates中有 <= 0的数就会stack overflow，所以题目中给定元素全是正整数。
int target，这个是我们的目标值， dfs的时候传入下一层是 target - num
int pos，这个是我们的position参数，因为题目要求必须从小到大排序，并且不能有重复，所以我们用pos函数来控制每层dfs不遍历之前已经跳过或者遍历过的元素

接下来就是复杂度分析。这道题的复杂度分析起来比较复杂....一刷的时候就没有好好思考。

首先我们假设这个数组candidate长为n，在其中有m个元素小于target，假设T(n) = find(target)，那么我们可以根据程序得到以下分析结果:

DFS Level 0: 我们首次调用辅助函数，这一层的count = 1
DFS Level 1: 这时候我们进入了辅助函数的for循环，在for循环里我们有一个pruning，当candidate[i] > target的时候，返回，所以这一层我们只对小于target的元素进行下一层DFS，如我们假设的，结果为m
DFS Level 2: 根据代码，我们上一层有一个target -= num，所以这一层的target其实都不一样。
1. 假设我们对candidate中最小的元素min进行分析，这时候新的target₁ = target - min，此时我们要继续计算在candidate数组中有多少元素小于新的target₁，假设这个数目为m₁，则在这一层我们要对小于target₁的m₁个数组进行下一层的DFS
2. 假如我们考虑其他非min的元素来计算总的复杂度时，这时候两层总共要进行1 + m(m₁ + m₂ + m₃ + ... + m_n)次调用。
由于每一层的target和m都在改变，以我的水平比较难计算出一个漂亮的公式，那么我就想办法简化一下：
1. 这里递归的最大深度是d= target / min，就是最深我们可以到 target / min这么多层DFS
2. Branching factor b = m， m是candidate数组里小于等于target的distinct元素的个数。其实这里多算了，每一层的m都在减少，而且是不规则减少
3. 我们利用DFS公式可以算出这里的Time Complexty = O(m^d)， Space Complexity = O(m)
4. 这只是一个worst case scenario，更精确的计算还需要再花时间。

Java:

Time Complexity - O(m^d), Space Complexity - O(m)， m is distinct elements in candidate[] which candidate[i] <= target， d = target / min element in candidate[]

public class Solution {

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

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

        if (candidates == null || candidates.length == 0) {

            return res;

        }

        Arrays.sort(candidates);

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

        combinationSum(res, comb, candidates, target, 0);

        return res;

    }

    private void combinationSum(List<List<Integer>> res, List<Integer> comb, int[] candidates, int target, int pos) {

        if (target < 0) {

            return;

        } else if (target == 0) {

            res.add(new ArrayList<>(comb));

        }

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

            int num = candidates[i];

            if (num > target) {

                return;

            }

            comb.add(num);

            combinationSum(res, comb, candidates, target - num, i);

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

        }

    }

}

题外话：

1/22/2016

看了地里一些Amazon的Video题目...感觉现在的new graduate孩子们好幸福，随便刷刷题就可以拿offer了，羡慕。但是在看leetcode的时候也发现有些大牛刷题时间有半年甚至1年。有些题目question提问时间是2014年，但在15年下半年还很活跃。在cnblogs里也看到一些人刷题刷了4遍+的。我也还是先好好刷题把，刷到五遍再出关。现在才刚第二遍开头，吃不到葡萄，不要说葡萄酸。

美东这个周末据说会有很大的暴风雪， winter storm Jonas，降雪量可能有10 - 18 inches，幸好周四提前买了好多吃喝备足了。车子加油，也有好几个加油站都卖空了。希望情况不要太严重。

三刷:

方法跟二刷一样。没有特意分析复杂度。

Java:

public class Solution {

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

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

        if (candidates == null) return res;

        Arrays.sort(candidates);

        getCombinations(res, new ArrayList<>(), candidates, target, 0);

        return res;

    }

    private void getCombinations(List<List<Integer>> res, List<Integer> list, int[] nums, int target, int pos) {

        if (target < 0) return;

        if (target == 0) {

            res.add(new ArrayList<>(list));

            return;

        }

        for (int i = pos; i < nums.length; i++) {

            if (nums[i] > target) break;   // Pruning

            if (i > pos && nums[i] == nums[i - 1]) continue;    // Pruning

            list.add(nums[i]);

            getCombinations(res, list, nums, target - nums[i], i);

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

        }

    }

}

Reference:

http://www.cis.upenn.edu/~matuszek/cit594-2012/Pages/backtracking.html

http://www.fas.harvard.edu/~cscie119/lectures/recursion.pdf

http://www3.cs.stonybrook.edu/~algorith/ <- Backtracking Template

https://leetcode.com/discuss/37071/accepted-16ms-c-solution-use-backtracking-easy-understand

https://leetcode.com/discuss/10141/a-solution-avoid-using-set

https://leetcode.com/discuss/23818/iterative-java-dp-solution

https://leetcode.com/discuss/59204/easy-to-understand-96%25-performance-java-solution

https://leetcode.com/discuss/42670/very-elegant-python-code-using-recursive-yield-iterator

https://leetcode.com/discuss/7181/what-time-complexity-recursive-solution-this-problem-how-get

http://yucoding.blogspot.com/2012/12/leetcode-question-16-combination-sum.html

http://zhaonanleetcode.blogspot.com/2014/06/leetcode-combination-sum-ii.html

巴特西

39. Combination Sum

最新文章

热门文章