Thinking process

empty array? yes

[2,2,3] == [2,3,2]? yes

how to find an answer?

• draw tree, the value of each node is target at this level
• if target < 0, return
• if target == 0, copy the list to result

Mistakes

1. don't forget to add the limitation that only consider the elements on the right
2. same value can be repeatedly added to the list, so index should be the same

public class Solution {
    public List<List<Integer>> combinationSum(int[] candidates, int target) {
        List<List<Integer>> result = new ArrayList<>();

        //validate input
        if (candidates.length == 0) return result;
        Arrays.sort(candidates);
        findCombinationSum(candidates, target, result, new ArrayList<>(), 0);

        return result;
    }

    private void findCombinationSum(int[] candidates, int target, List<List<Integer>> result, List<Integer> list, int index){
        //end conditions
        if (target < 0) {
            return;
        } else if (target == 0) {
            result.add(new ArrayList<>(list));
            return;
        }

        for (int i = index; i < candidates.length; ++i) {
            list.add(candidates[i]);
            findCombinationSum(candidates, target - candidates[i], result, list, i);
            list.remove(list.size() - 1);
        }
    }
}