Combination Sum: the idea to remember.

The core insight

Recurse using nondecreasing candidate indices, keeping the current index available for reuse.

Why it works

A fixed index order removes permutations of the same combination while repeated selection permits unlimited reuse.

The mistake to avoid

Positive candidates ensure recursion progresses. Reusing a value means staying at its index, not restarting at zero.

Commented Java solution

Use java.util.* imports and a surrounding solution class. Tree snippets assume the standard TreeNode definition; linked lists use ListNode and Clone Graph uses a Node with val and neighbors; Copy Random List uses Node with val, next and random. Read the input assumptions above.

// Java reference adapted from neetcode-gh/leetcode (MIT).
// Recurse using nondecreasing candidate indices, keeping the current index available for reuse.
public List<List<Integer>> combinationSum(int[] candidates, int target) {
    List<List<Integer>> ans = new ArrayList<List<Integer>>();
    List<Integer> cur = new ArrayList();
    backtrack(candidates, target, ans, cur, 0);
    return ans;
}

public void backtrack(
    int[] candidates,
    int target,
    List<List<Integer>> ans,
    List<Integer> cur,
    int index
) {
    if (target == 0) {
        ans.add(new ArrayList(cur));
    } else if (target < 0 || index >= candidates.length) {
        return;
    } else {
        cur.add(candidates[index]);
        backtrack(candidates, target - candidates[index], ans, cur, index);

        cur.remove(cur.get(cur.size() - 1));
        backtrack(candidates, target, ans, cur, index + 1);
    }
}

Java reference adapted from neetcode-gh/leetcode · MIT license

Make the next connection