Combination Sum

题目地址：

https://leetcode.com/problems/combination-sum/#/description

题目：

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]
]

解题思路：

这道题是典型的backtracking，先排序，当某个元素的值大于target的时候，就要break。这道题还有一个follow up：就是当不能够有重复的解的时候，需要做一下处理。

代码：

public List<List<Integer>> combinationSum(int[] candidates, int target) {
    List<List<Integer>> rst = new ArrayList<>();
    if(candidates == null || candidates.length == 0){
        return rst;
    }
    Arrays.sort(candidates);
    List<Integer> list = new ArrayList<>();
    helper(rst, list, candidates, target, 0);
    return rst;
}
private void helper(List<List<Integer>> rst, List<Integer> list, int[] candidates, int target, int pos) {
    if(target == 0){
        rst.add(new ArrayList<>(list));
        return;
    }
    for(int i = pos; i <= candidates.length - 1; i++){
        if(target < candidates[i]){
            break;
        }
        list.add(candidates[i]);
        helper(rst, list, candidates, target - candidates[i], i);
        list.remove(list.size() - 1);
    }
}

Follow up:

public List<List<Integer>> combinationSum2(int[] candidates, int target) {
    List<List<Integer>> rst = new ArrayList<>();
    if(candidates == null || candidates.length == 0){
        return rst;
    }
    Arrays.sort(candidates);
    List<Integer> list = new ArrayList<>();
    helper(rst, list, candidates, target, 0);
    return rst;
}
private void helper(List<List<Integer>> rst, List<Integer> list, int[] candidates, int target, int pos) {
    if(target == 0){
        rst.add(new ArrayList<>(list));
        return;
    }
    for(int i = pos; i <= candidates.length - 1; i++){
        if(target < candidates[i]){
            break;
        }
        if(i != pos && candidates[i - 1] == candidates[i]){
            continue;
        }
        list.add(candidates[i]);
        helper(rst, list, candidates, target - candidates[i], i + 1);
        list.remove(list.size() - 1);
    }
}

Follow up 2：
Find all possible combinations of k numbers that add up to a number n, given that only numbers from 1 to 9 can be used and each combination should be a unique set of numbers.

public List<List<Integer>> combinationSum3(int k, int n) {
    List<List<Integer>> rst = new ArrayList<>();
    if(k == 0){
        return rst;
    }
    List<Integer> list = new ArrayList<>();
    helper(rst, list, n, k, 1);
    return rst;
}
private void helper(List<List<Integer>> rst, List<Integer> list, int target, int size, int pos){
    if(target == 0 && list.size() == size){
        rst.add(new ArrayList<>(list));
        return;
    }
    for(int i = pos; i <= 9; i++){
        list.add(i);
        helper(rst, list, target - i, size, i + 1);
        list.remove(list.size() - 1);
    }
}

Follow up 3:

Given an integer array with all positive numbers and no duplicates, find the number of possible combinations that add up to a positive integer target.

Example:

nums = [1, 2, 3]
target = 4

The possible combination ways are:
(1, 1, 1, 1)
(1, 1, 2)
(1, 2, 1)
(1, 3)
(2, 1, 1)
(2, 2)
(3, 1)

Note that different sequences are counted as different combinations.

Therefore the output is 7.

首先最直接的想法是backtracking：

public int combinationSum4(int[] nums, int target) {
    if(nums == null || nums.length == 0){
        return 0;
    }
    List<List<Integer>> rst = new ArrayList<>();
    Arrays.sort(nums);
    helper(rst, new ArrayList<Integer>(), nums, target);
    return rst.size();
}

private void helper(List<List<Integer>> rst, List<Integer> list, int[] nums, int target){
    if(target == 0){
        rst.add(new ArrayList<>(list));
        return;
    }
    for(int i = 0; i <= nums.length - 1; i++){
        if(target < nums[i]){
            return;
        }
        list.add(nums[i]);
        helper(rst, list, nums, target - nums[i]);
        list.remove(list.size() - 1);
    }
}

但是backtracking会超时。

这里可以用dp来解决：

public int combinationSum4(int[] nums, int target) {
    Arrays.sort(nums);
    int[] dp = new int[target + 1];
    for(int i = 0; i <= target; i++){
        for(int num : nums){
            if(num > i){
                break;
            }
            if(num == i){
                dp[i] += 1;
            }
            if(num < i){
                dp[i] += dp[i - num];
            }
        }
    }
    return dp[target];
}