67. Combination Sum

MediumArray Backtracking

Given an array of distinct positive integers candidates and a positive integer target, return every unique combination of candidates whose sum is exactly target.

Any candidate may be used as many times as you like. Two combinations are the same if they use each number the same number of times, so [2,3,3] and [3,2,3] count once. Return the combinations in any order; the numbers inside a combination may also be in any order. If no combination works, return an empty list.

Example 1

Input: candidates = [3,4,5], target = 8
Output: [[3,5],[4,4]]

Explanation: 3 + 5 = 8 and 4 + 4 = 8; the 4 is reused.

Example 2

Input: candidates = [2,3], target = 6
Output: [[2,2,2],[3,3]]

Example 3

Input: candidates = [2], target = 1
Output: []

Constraints

1 <= candidates.length <= 30
1 <= candidates[i] <= 40
All values in candidates are distinct
1 <= target <= 40
Every test has fewer than 150 valid combinations

Follow-up: Now each candidate may be used at most once and candidates may contain duplicates. How do you still avoid repeated combinations?

💡 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