LC216.md

Problem: Combination Sum III

Difficulty: Medium

Description:

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

• Only numbers 1 through 9 are used.
• Each number is used at most once. 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:

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

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

Constraints:

2 <= k <= 9
1 <= n <= 60

Solutions:

We can use backtracking algorithm, to avoid double counting and having repeated elements in the solution.

def combinationSum3(k, n):
    """
    :type k: int
    :type n: int
    :rtype: List[List[int]]
    """
    ans = []

    def backtrack(tot, arr):
        if tot == n and len(arr) == k:
            ans.append(arr)
            return

        elif tot > n or len(arr) > k:
            return

        for i in range(1, 10):
            if not arr or i > arr[-1]:
                backtrack(tot + i, arr + [i])

    backtrack(0, [])

    return ans