[LeetCode] Combination Sum III

Problem: 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.

Example:

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

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.

Input: k = 4, n = 1
Output: []
Explanation: There are no valid combinations.
Using 4 different numbers in the range [1,9], the smallest sum we can get is 1+2+3+4 = 10 and since 10 > 1, there are no valid combination.

Approach: We can use backtracking here. The recursive relation would be something like below:

f(k, n, i) = f(k - 1, n - i, i - j), where j is (i + 1)....9

Implementation in C#:

    public IList<IList<int>> CombinationSum3(int k, int n)

    {

        var currNums = new List<int>();

        var result = new List<IList<int>>();

        this.CombinationSum(k, n, currNums, 1, result);

        return result;

    }

    private void CombinationSum(int k,

                                int n,

                                List<int> currNums,

                                int currNum,

                                List<IList<int>> result)

    {

        if (currNums.Count == k)

        {

            if (n == 0)

            {

                Console.WriteLine($"Adding {string.Join(", ", currNums)}");

                result.Add(new List<int>(currNums));

            }

            return;

        }

        for (int i = currNum; i <= 9; ++i)

        {

            if (n - i >= 0)

            {

                currNums.Add(i);

                this.CombinationSum(k, n - i, currNums, i + 1, result);

                currNums.RemoveAt(currNums.Count - 1);

            }

            else

            {

                break;

            }

        }

    }

Complexity: O(2 ^ 9)