Combination Sum

Problem

Given an array of distinct positive integers candidates and a positive integer target, return all unique combinations that sum to target. The same number can be chosen any number of times.

Constraints

• 1 ≤ candidates.length ≤ 30
• all distinct

Approach — Backtracking

This is a Backtracking problem. The idea: build candidates one choice at a time and abandon a branch the moment it can't lead to a valid answer. Work through the reference code below line by line, then re-derive it yourself in the editor — that's how the pattern sticks.

Complexity: exponential worst case.

Solution code

Python

class Solution:
    def combinationSum(self, candidates, target):
        candidates.sort()
        res = []
        def bt(start, cur, rem):
            if rem == 0:
                res.append(cur[:]); return
            for i in range(start, len(candidates)):
                if candidates[i] > rem:
                    break
                cur.append(candidates[i])
                bt(i, cur, rem - candidates[i])
                cur.pop()
        bt(0, [], target)
        return res

Java

import java.util.*;

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

    private void bt(List<List<Integer>> out, List<Integer> cur, int[] c, int rem, int start) {
        if (rem == 0) { out.add(new ArrayList<>(cur)); return; }
        for (int i = start; i < c.length && c[i] <= rem; i++) {
            cur.add(c[i]);
            bt(out, cur, c, rem - c[i], i);
            cur.remove(cur.size() - 1);
        }
    }
}

Practice it

Reading a solution isn't the same as being able to write it under pressure. Open this problem in the in-browser editor, hide the solution, and solve it from scratch — your code runs against real test cases instantly.