LeetCode 39. Combination Sum

Problem

LeetCode 39. Combination Sum

1. 题目简述

给出一个无重复的正整数数组A，给出一个target，找出和为target的所有不重复的可能组合（每个数字使用次数不限）。例如：

Input: candidates = [2,3,5], target = 8,
A solution set is:
[
[2,2,2,2],
[2,3,3],
[3,5]
]

2. 算法思路

这道题是combination sum系列的第一题，看似有点像背包问题，实际上又不是。这道题问的是所有组合，某些DP问题也是求所有的组合之类的，但是本题要求不能有相同元素组成的组合，且找不到所谓的最优子问题结构，因此所以并不是DP问题（等复习到背包问题再回过来看）。

Brute Force（行不通）

首先，最容易想到的就是能不能用暴力破解法呢？答案肯定是不行的，由于每个数字取的次数不限，所以直接暴力破解不可取，需要优化。

回溯

那么为什么会想到回溯呢？没有为什么，因为回溯能做出来这种需要遍历所有可能的问题。就这么简单。

对于一个数组A和某个target值，我们希望找出target所有的组合可能，假设F(int[] A, int start, int target)为从数组A中以start为起点找出target的所有可能组合，思路如下。

1. 对A从小到大进行排序，取A[0]作为第一个数，那么我们当前的目标是F(A, 0, target - A[0])；将其结果和A[0]放在一起作为第一种解。
2. 然后取A[1]作为第一个数，然后我们目标是F(A, 1, target - A[1])。不从0开始是因为如果取了0，就会和第一步中的某种solution重复，故不取。
3. 终止条件为target == 0，最终结果添加一条；target < 0，回溯上去继续搞。

3. 解法

1. 暴力解法（Pass）
2. 回溯

class Solution {
    List<List<Integer>> res;
    public List<List<Integer>> combinationSum(int[] candidates, int target) {
        res = new ArrayList();
        LinkedList<Integer> nums = new LinkedList(); //删除last回溯的时候方便
        Arrays.sort(candidates);

        backtracking(candidates, target, 0, 0, nums);

        return res;
    }

    private void backtracking(int[] candidates, int target, int sum, int startIndex, LinkedList<Integer> nums) {
        for (int i = startIndex; i < candidates.length; i++){
            sum += candidates[i];
            nums.add(candidates[i]);

            if (sum < target) {
                backtracking(candidates, target, sum, i, nums);
                sum -= candidates[i];
                nums.removeLast();
                continue;
            } else if (sum == target) {
                res.add(new ArrayList(nums));
            }

            nums.removeLast();
            return;
        }
    }
}