Problem

• lintCode: might have duplicate candidates
• leetCode: no duplicate candidates
• 差别: 一句话 if (i != 0 && nums[i - 1] == nums[i]) continue;

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

思路

1. 为什么使用dfs?
   1. 因为这个问题是一个组合问题, 需要搜索整个数组.
2. 为什么需要start Index?
   1. 因为以某个元素为开头的subset, 该元素之前的元素已经使用过了, 不需要再次使用.
3. 给数组排序, 使得相同的元素凑在一起
4. 每一层都从startIndex开始遍历, 当当前元素和上一个元素一样的时候, 跳过. 因为可以使用上一个元素无数次
5. 当target > 0 的时候, 继续从当前index开始搜索
6. 当target == 0, 找到目标, 加入result中

    public List<List<Integer>> combinationSum(int[] candidates, int target) {
        List<List<Integer>> result = new ArrayList<>();
        if (candidates == null || candidates.length == 0) return result;

        Arrays.sort(candidates);
        helper(candidates, result, new ArrayList<Integer>(), target, 0);
        return result;
    }

    private void helper(int[] nums, List<List<Integer>> result, List<Integer> path, int target, int startIndex) {

        for (int i = startIndex; i < nums.length; i++) {
            if (i != 0 && nums[i - 1] == nums[i]) continue;

            path.add(nums[i]);
            target -= nums[i];

            if (target == 0) {
                result.add(new ArrayList<Integer>(path));
            } else if (target > 0) {
                helper(nums, result, path, target, i);
            } 

            target += nums[i];
            path.remove(path.size() - 1);
        }
    }