Combination Sum

MediumArray Backtracking

A post office kiosk sells stamps in a few distinct denominations, candidates, with an unlimited supply of each. A customer owes exactly target cents of postage and wants to see every way to make up that amount.

Return all unique combinations of denominations that add up to exactly target. A denomination may be used any number of times. Two combinations are the same when they use each denomination the same number of times, so [3,3,5] and [5,3,3] count once. Return the combinations in any order, with the values inside each combination in any order. If nothing adds up to target, return an empty list.

Example 1

Input: candidates = [2,5,3], target = 9
Output: [[2,2,2,3],[2,2,5],[3,3,3]]

Explanation: Three different combinations reach 9 cents, and the 2-cent stamp is reused in two of them.

Example 2

Input: candidates = [4,6], target = 12
Output: [[4,4,4],[6,6]]

Explanation: Either three 4-cent stamps or two 6-cent stamps.

Example 3

Input: candidates = [6], target = 10
Output: []

Explanation: Multiples of 6 jump from 6 straight to 12, so 10 cents cannot be paid exactly.

Constraints

There are between 1 and 30 denominations, all distinct.
Each denomination is between 1 and 40 cents.
target is between 1 and 40.
No test has more than 149 valid combinations.

Follow-up: Now the kiosk has only one stamp for each entry in candidates, and two entries may share a denomination. How do you still avoid listing the same combination twice?

💡 Hint 1

To avoid producing the same combination in different orders, only ever pick candidates at or after the index of the last one you picked.

💡 Hint 2

Backtrack with (start, remaining): for each i >= start, choose candidates[i] and recurse with (i, remaining - candidates[i]). Passing i (not i + 1) allows reuse.

💡 Hint 3

Sort the candidates first so you can stop the loop as soon as a candidate exceeds remaining.

Try it yourself first ✎

Solutions stick better after a real attempt. Peek when you're ready.

Approach

Backtracking over a sorted copy of candidates. The recursive step (start, remaining) tries each index i >= start: add candidates[i] to the path and recurse with (i, remaining - candidates[i]). Staying at i allows reuse, and never going back below start means every combination is generated in non-decreasing order, exactly once. When remaining hits 0, record a copy of the path. Since the list is sorted, the loop can break as soon as candidates[i] > remaining.

Time Exponential in target / min(candidates) in the worst case; proportional to the size of the search treeSpace O(target / min(candidates)) recursion depth, besides the output

function combinationSum(candidates, target) {
  const nums = [...candidates].sort((a, b) => a - b);
  const result = [];
  const path = [];
  const search = (start, remaining) => {
    if (remaining === 0) {
      result.push([...path]);
      return;
    }
    for (let i = start; i < nums.length && nums[i] <= remaining; i++) {
      path.push(nums[i]);
      search(i, remaining - nums[i]);
      path.pop();
    }
  };
  search(0, target);
  return result;
}

class Solution {
    public List<List<Integer>> combinationSum(int[] candidates, int target) {
        int[] nums = candidates.clone();
        Arrays.sort(nums);
        List<List<Integer>> result = new ArrayList<>();
        search(nums, 0, target, new ArrayList<>(), result);
        return result;
    }

    private void search(int[] nums, int start, int remaining, List<Integer> path, List<List<Integer>> result) {
        if (remaining == 0) {
            result.add(new ArrayList<>(path));
            return;
        }
        for (int i = start; i < nums.length && nums[i] <= remaining; i++) {
            path.add(nums[i]);
            search(nums, i, remaining - nums[i], path, result);
            path.remove(path.size() - 1);
        }
    }
}

/**
 * @param {number[]} candidates
 * @param {number} target
 * @return {number[][]}
 */
function combinationSum(candidates, target) {

}

Ctrl/⌘ + ' run · Ctrl/⌘ + Enter submit