Problem of The Day: Combination Sum III

Problem Statement

leetcode problem link

My Solution [Accepted]

class Solution:
    def combinationSum3(self, k: int, n: int) -> List[List[int]]:
        arr = [i for i in range(1, 10)]
        res = []

        def backtrack(i, curr):
            if sum(curr) == n and len(curr) == k:
                res.append(curr[:])
                return

            for j in range(i, 10):
                curr.append(j)
                backtrack(j + 1, curr)
                curr.pop()

        backtrack(1, [])

        return res

public class Solution {
    private IList<IList<int>> Result { set; get; } = new List<IList<int>>();
    private int KValue { set; get; }
    private int NValue { set; get; }

    public void Backtrack(int number, List<int> current) {
        if (current.Count == KValue && current.Sum() == NValue) {
            Result.Add(new List<int>(current));
            return;
        }
        for (int i = number; i < 10; i++) {
            current.Add(i);
            Backtrack(i + 1, current);
            current.Remove(i);
        }
    }

    public IList<IList<int>> CombinationSum3(int k, int n) {
        KValue = k;
        NValue = n;
        Backtrack(1, new List<int>());
        return Result;
    }
}

Improve CSharp code

public class Solution
{
    private IList<IList<int>> _result = new List<IList<int>>();

    public IList<IList<int>> CombinationSum3(int k, int n)
    {
        _result = new List<IList<int>>();   // reset for each call
        Backtrack(1, k, n, new List<int>(), 0);
        return _result;
    }

    private void Backtrack(int start, int k, int target, List<int> current, int currentSum)
    {
        // If we hit the required size
        if (current.Count == k)
        {
            if (currentSum == target)
                _result.Add(new List<int>(current));
            return;
        }

        // Prune: if sum already exceeds target, stop
        if (currentSum > target)
            return;

        for (int i = start; i <= 9; i++)
        {
            // Prune: if even adding the smallest possible numbers can't reach k elements
            if (current.Count + (10 - i) < k)
                break;

            current.Add(i);
            Backtrack(i + 1, k, target, current, currentSum + i);
            current.RemoveAt(current.Count - 1); // safe removal
        }
    }
}

Editorial

Approach: Backtracking

class Solution:
    def combinationSum3(self, k: int, n: int) -> List[List[int]]:
        results = []

        def backtrack(remain, comb, next_start):
            if remain == 0 and len(comb) == k:
                # make a copy of current combination
                # Otherwise the combination would be reverted in other branch of backtracking.
                results.append(list(comb))
                return
            elif remain < 0 or len(comb) == k:
                # exceed the scope, no need to explore further.
                return

            # Iterate through the reduced list of candidates.
            for i in range(next_start, 9):
                comb.append(i + 1)
                backtrack(remain - i - 1, comb, i + 1)
                # backtrack the current choice
                comb.pop()

        backtrack(n, [], 0)

        return results