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

        findCombinationSum(candidates, target, 0, result, temp);
        return result;
    }

    public void findCombinationSum(int[] nums, int target, int index, List<List<Integer>> result, List<Integer> temp)
    {

        // Base condition 1: when target becomes 0
        if(target == 0)
        {
            result.add(new ArrayList<>(temp));
            return;
        }

        // Base condition 2: when we reach end of the array
        if(index == nums.length)
            return;

        if(nums[index] <= target)
        {
            // pick the element 
            temp.add(nums[index]);
            findCombinationSum(nums, target - nums[index], index, result, temp);

            // do not pick the element
            temp.remove(temp.size()-1);
        }
        findCombinationSum(nums, target, index+1, result, temp);
        return;
    }
}