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

        if (candidates.length == 0) {
            return answer;
        }

        Arrays.sort(candidates);
        int currSum = 0;
        combinationSumBackTrack(answer, new ArrayList<Integer>(), candidates, target, currSum, 0);
        return answer;
    }

    private void combinationSumBackTrack(List<List<Integer>> answer, List<Integer> currentStore, int[] candidates, int target, int currSum, int currentIndex) {

        if (currSum == target) {
            answer.add(new ArrayList<>(currentStore));
            return;
        }

        for (int i = currentIndex; i < candidates.length; i++) {
            if (currSum + candidates[i] <= target) {
                currentStore.add(candidates[i]);
                combinationSumBackTrack(answer, currentStore, candidates, target, currSum + candidates[i], i);
                currentStore.remove(Integer.valueOf(candidates[i]));
            }
        }
    }
}