Combination Sum

LEETCODE PROBLEM SOLVING
PROBLEM-> COMBINATION SUM
  import java.util.*;

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

    private void backtrack(List<List<Integer>> result,
                           List<Integer> temp,
                           int[] candidates,
                           int target,
                           int start) {

        // base case
        if (target == 0) {
            result.add(new ArrayList<>(temp));
            return;
        }

        if (target < 0) return;

        for (int i = start; i < candidates.length; i++) {
            // choose
            temp.add(candidates[i]);

            // explore (same i → reuse allowed)
            backtrack(result, temp, candidates, target - candidates[i], i);

            temp.remove(temp.size() - 1);
        }
    }
}