algoadvance

Leetcode 216. Combination Sum III

Problem Statement

LeetCode Problem 216: Combination Sum III

Description:
Find all possible combinations of k numbers that add up to a number n, given that only numbers from 1 to 9 can be used and each combination should be a unique set of numbers.

You should return all possible combinations in any order.

Example:

Input: k = 3, n = 7
Output: [[1,2,4]]

Input: k = 3, n = 9
Output: [[1,2,6], [1,3,5], [2,3,4]]

Constraints:

Clarifying Questions

  1. Q: Can numbers repeat in the combinations? A: No, each number from 1 to 9 can be used only once in each combination.

  2. Q: Is there a need to sort the combinations? A: No, the output can be any order as stated in the problem description.

  3. Q: What if no combinations are possible? A: Should return an empty list in that scenario.

Strategy

We will use backtracking to explore all possible combinations of numbers. The algorithm will proceed as follows:

  1. Start with an empty combination and a starting number (1 to 9).
  2. Recursively add numbers to the combination until the length k is reached.
  3. If the current combination sums to n, add it to the result list.
  4. If the sum exceeds n or the length exceeds k, backtrack.

This approach ensures that we explore all possible combinations and backtrack whenever the current sum exceeds the target or the length exceeds k.

Code

Here’s a C++ implementation for the problem:

#include <vector>
using namespace std;

class Solution {
public:
    vector<vector<int>> combinationSum3(int k, int n) {
        vector<vector<int>> result;
        vector<int> combination;
        backtrack(result, combination, k, n, 1);
        return result;
    }

private:
    void backtrack(vector<vector<int>>& result, vector<int>& combination, int k, int target, int start) {
        if (combination.size() == k) {
            if (target == 0) {
                result.push_back(combination);
            }
            return;
        }
        
        for (int i = start; i <= 9; ++i) {
            combination.push_back(i);
            backtrack(result, combination, k, target - i, i + 1);
            combination.pop_back(); // backtrack
        }
    }
};

Time Complexity

The time complexity of this solution is derived from the nature of the backtracking algorithm:

In the worst case, the number of combinations explored is C(9, k) = 9! / ((9 - k)! * k!), which is combinatorial in nature. Thus, for k <= 9, the time complexity can be considered exponential, or O(2^N) where N = 9.

Space Complexity

The space complexity mainly involves the space utilized by the recursion call stack and the temporary list to hold combinations, both of which can reach up to O(k) in depth and size respectively. Additionally, the result list stores all valid combinations. Thus, the overall space complexity can be considered O(N^k), again combinatorial in nature.

Cut your prep time in half and DOMINATE your interview with AlgoAdvance AI