216. Combination Sum III

Medium

Problem Description

Find all valid combinations of k numbers that sum up to n such that the following conditions are true:

Return a list of all possible valid combinations. The list must not contain the same combination twice, and the combinations may be returned in any order.

Examples

Example 1:
Input: k = 3, n = 7
Output: [[1,2,4]]
Explanation:
1 + 2 + 4 = 7
There are no other valid combinations.

Example 2:
Input: k = 3, n = 9
Output: [[1,2,6],[1,3,5],[2,3,4]]
Explanation:
1 + 2 + 6 = 9
1 + 3 + 5 = 9
2 + 3 + 4 = 9
There are no other valid combinations.

Example 3:
Input: k = 4, n = 1
Output: []
Explanation: There are no valid combinations.
Jump to Solution: Python Java C++ JavaScript C#

Python Solution


def combinationSum3(k: int, n: int) -> List[List[int]]:
    def backtrack(start: int, target: int, path: List[int]) -> None:
        if len(path) == k:
            if target == 0:
                result.append(path[:])
            return
        
        for i in range(start, 10):
            if i > target:
                break
            path.append(i)
            backtrack(i + 1, target - i, path)
            path.pop()
    
    result = []
    backtrack(1, n, [])
    return result

Java Solution


class Solution {
    private List> result = new ArrayList<>();
    
    public List> combinationSum3(int k, int n) {
        backtrack(k, n, 1, new ArrayList<>());
        return result;
    }
    
    private void backtrack(int k, int target, int start, List path) {
        if (path.size() == k) {
            if (target == 0) {
                result.add(new ArrayList<>(path));
            }
            return;
        }
        
        for (int i = start; i <= 9; i++) {
            if (i > target) {
                break;
            }
            path.add(i);
            backtrack(k, target - i, i + 1, path);
            path.remove(path.size() - 1);
        }
    }
}

C++ Solution


class Solution {
public:
    vector> combinationSum3(int k, int n) {
        vector> result;
        vector path;
        backtrack(k, n, 1, path, result);
        return result;
    }
    
private:
    void backtrack(int k, int target, int start, vector& path, 
                  vector>& result) {
        if (path.size() == k) {
            if (target == 0) {
                result.push_back(path);
            }
            return;
        }
        
        for (int i = start; i <= 9; i++) {
            if (i > target) {
                break;
            }
            path.push_back(i);
            backtrack(k, target - i, i + 1, path, result);
            path.pop_back();
        }
    }
};

JavaScript Solution


/**
 * @param {number} k
 * @param {number} n
 * @return {number[][]}
 */
var combinationSum3 = function(k, n) {
    const result = [];
    
    const backtrack = (start, target, path) => {
        if (path.length === k) {
            if (target === 0) {
                result.push([...path]);
            }
            return;
        }
        
        for (let i = start; i <= 9; i++) {
            if (i > target) {
                break;
            }
            path.push(i);
            backtrack(i + 1, target - i, path);
            path.pop();
        }
    };
    
    backtrack(1, n, []);
    return result;
};

C# Solution


public class Solution {
    private IList> result = new List>();
    
    public IList> CombinationSum3(int k, int n) {
        Backtrack(k, n, 1, new List());
        return result;
    }
    
    private void Backtrack(int k, int target, int start, List path) {
        if (path.Count == k) {
            if (target == 0) {
                result.Add(new List(path));
            }
            return;
        }
        
        for (int i = start; i <= 9; i++) {
            if (i > target) {
                break;
            }
            path.Add(i);
            Backtrack(k, target - i, i + 1, path);
            path.RemoveAt(path.Count - 1);
        }
    }
}

Complexity Analysis

Solution Explanation

This problem is solved using backtracking:

Key Points

Optimization Tips

Edge Cases