216. Combination Sum III

Problem Description

The problem requires us to find all unique combinations of k different numbers, which sum up to a target number n, using only numbers from 1 to 9. Each number can be used at most once in any combination. The resulting combinations are to be returned in a list, where the order of combinations does not matter, and no combination is repeated.

For example, if k=3 and n=7, we have to find all unique combinations of three distinct numbers between 1 and 9 that add up to 7. One such valid combination could be [1, 2, 4] because 1+2+4=7.

Flowchart Walkthrough

First, let's pin down the algorithm using the Flowchart. Here's a step-by-step walkthrough:

Is it a graph?

No: The problem does not involve nodes and edges typically found in graph problems.

Need to solve for kth smallest/largest?

No: This problem is about finding all possible combinations that sum to a specific value, not about the kth smallest or largest element.

Involves Linked Lists?

No: The problem does not involve linked lists. It deals with finding combinations of numbers.

Does the problem have small constraints?

Yes: The problem limits the numbers to choose from 1 to 9 and requires choosing exactly k numbers. This indicates potentially small constraints suitable for exploring all combinations directly.

Brute force / Backtracking?

Yes: Given the nature of the problem, finding all valid combinations fits the pattern of brute force or backtracking, where we need to explore all potential sets of numbers that meet the given criteria.

Conclusion: The flowchart suggests using a backtracking approach to generate all valid combinations that sum up to the specific target, taking into account that exactly k numbers must be used.

Intuition

To find the solution, we can utilize a Depth First Search (DFS) algorithm. DFS will help us explore all possible combinations of numbers recursively while adhering to the constraints. Here's the intuition behind using DFS for this problem:

We begin by considering numbers from 1 to 9 and use each of them as a starting point of a combination.
To build a combination, we add a number to the current combination (t in the given code) and recursively call the DFS function to add the next number.
- While adding the new number, we have three conditions to check:
  1. We must not exceed the target sum n.
  2. We should not use more than k numbers.
  3. We cannot use numbers greater than 9.
If the sum of numbers in the current combination equals n and we have used exactly k numbers, then we found a valid combination which we add to the answer list (ans).
After exploring a number's inclusion, we backtrack by removing the number from the current combination and exploring the possibility of not including that number.
Through this process of including and excluding each number, and backtracking after exploring each possibility, we ensure that all valid combinations are found.
Each combination is built up incrementally from the smaller numbers towards the larger ones to avoid repeated combinations and maintain uniqueness.

The beauty of DFS in this situation is that it inherently avoids duplicates and handles the "each number used at most once" constraint by the recursive nature of its implementation. DFS explores each branch fully (one specific number added vs. not added) before backtracking, which helps cover all potential unique combinations without repetition.

Learn more about Backtracking patterns.

Solution Approach

The provided solution uses a Depth First Search (DFS) algorithm to explore all possible unique combinations of numbers that add up to n using at most k numbers. Here is a step-by-step breakdown of the approach, referring to specific parts of the implementation:

DFS Function: The function dfs(i: int, s: int) is a recursive function where i represents the current number that we are considering adding to the combination, and s is the remaining sum that we need to achieve. The solution initializes the function by calling dfs(1, n).
Base Conditions:
- The first base condition checks whether the remaining sum s is 0. If s is 0 and we have exactly k numbers in our temporary combination t, then we have found a valid combination. We then append a a copy of t (using t[:] to create a copy) to our answers list ans.
- The second base condition checks whether the current number i is greater than 9 or i is greater than the remaining sum s or we have already selected k numbers. In any of these cases, the function returns without making further recursive calls since no valid combination can be completed under these conditions.
Choosing the Current Number:
- We add the current number i to our temporary combination t. This is the "exploring the possibility of including the number" part of the DFS.
Recursive Call for Next Number:
- After including the current number, we make a recursive call to dfs(i + 1, s - i). This call will explore combinations where the current number i is part of the solution. By passing i + 1, we are ensuring that the same number is not used more than once. By passing s - i, we are reducing the sum by the value of the number we've included.
Backtracking:
- After the recursive call, we backtrack by removing the last number that we added — t.pop(). This is where we explore the possibility of excluding the current number.
Recursive Call without the Current Number:
- Another recursive call dfs(i + 1, s) is then made. This call will explore combinations that exclude the current number i.
Initialization:
- The function maintains a list ans to collect all valid combinations found by the DFS.
- A list t is used to build a temporary combination that is being explored.
Return Result:
- Once the initial call to dfs(1, n) has completed, all possible combinations have been explored, and the ans list contains all valid combinations as required by the problem. This list is returned as the final result.

Through the combination of recursive DFS, building combinations incrementally, making sure that each number is used at most once, and backtracking after exploring each possibility, the solution efficiently finds all the valid combinations that sum up to n. The use of a temporary list t for tracking the current combination and the answer list ans are examples of data structures used in this problem to store intermediate and final results, respectively.

Ready to land your dream job?

Unlock your dream job with a 2-minute evaluator for a personalized learning plan!

Start Evaluator

Example Walkthrough

Let's consider a small example to illustrate the solution approach with k=2 and n=5. We need to find all unique pairs of numbers from 1 to 9 that sum up to 5.

Initialization: The ans list is initialized, which will store all valid combinations. The temporary combination list t is also initialized and the function dfs(1, 5) is called to begin the search for combinations that sum up to 5.
First Call to DFS: dfs(1, 5) represents the state where we are considering whether to include the number 1 in our combination and the remaining sum to reach our target n is 5. At this state, two branches of recursive calls will occur: one where we include the number 1 and another where we don't.
Including the Number '1': We include 1 to our temporary list t which is now [1], and the remaining sum s becomes 4. We call dfs(2, 4) to explore next numbers.
Recursive Call dfs(2, 4): Now we are evaluating whether to include the number 2. We choose to include 2, so t updates to [1, 2] and call dfs(3, 2) because now the remaining sum s is 2.
Base Condition Met: The recursive call dfs(3, 2) will recursively lead to a point where the remaining sum s is 0, and we have exactly 2 numbers in t. When t = [1, 4], s becomes 0. We add [1, 4] to ans, which is one valid combination.
Backtracking: After adding [1, 4] to ans, we backtrack by removing 4 from t. Now we have t = [1] again, and we call dfs(3, 5) since we still need to explore combinations starting with 1 without including 4.
Not Including the Number '1': We also need to consider combinations that do not include 1. After the first branch is fully explored with 1 in t, we remove 1 to explore the other branch. We call dfs(2, 5) to move on to the next number without including 1.
Exploring Further Combinations: The process of including and excluding numbers continues, now starting from 2 and exploring combinations [2, 3], [3, 2], ..., etc., until all valid pairs are found. This results in finding another valid pair [2, 3].
Return Result: Once all numbers from 1 to 9 have been considered through recursive calls and backtracking, the search is complete. The ans list which stored all valid combinations ([[1, 4], [2, 3]]) is returned.

At the end of execution, the returned value is [[1, 4], [2, 3]], which includes all unique combinations of 2 different numbers that sum up to 5.

This example walkthrough demonstrates the step-by-step approach taken by the DFS algorithm to explore all possibilities of including or excluding each number, checking for base conditions, backtracking as necessary, and ultimately collecting all the valid combinations into the answer list.

Solution Implementation

1from typing import List
2
3class Solution:
4    def combinationSum3(self, k: int, n: int) -> List[List[int]]:
5        # Helper function to perform depth-first search
6        def dfs(start: int, remaining_sum: int):
7            # If the remaining sum is 0 and we have 'k' numbers, we found a valid combination
8            if remaining_sum == 0 and len(combination) == k:
9                results.append(combination[:])  # Add a copy of the current combination
10                return
11            # If we have gone past 9, if the current number is greater than the remaining sum, 
12            # or if we already have 'k' numbers, back out of the recursion
13            if start > 9 or start > remaining_sum or len(combination) >= k:
14                return
15            # Include the current number and continue the search
16            combination.append(start)
17            dfs(start + 1, remaining_sum - start)
18            # Exclude the current number (backtrack) and continue the search
19            combination.pop()
20            dfs(start + 1, remaining_sum)
21
22        # This list holds all combinations found
23        results = []
24        # The current combination being explored
25        combination = []
26        # Start the search with 1 as the smallest number and 'n' as the target sum
27        dfs(1, n)
28        return results
29
30# Example usage:
31# sol = Solution()
32# print(sol.combinationSum3(3, 7))  # Output: [[1, 2, 4]]
33# print(sol.combinationSum3(3, 9))  # Output: [[1, 2, 6], [1, 3, 5], [2, 3, 4]]
34

1class Solution {
2    // List to store the final combinations
3    private List<List<Integer>> combinations = new ArrayList<>();
4    // Temporary list for the current combination
5    private List<Integer> currentCombination = new ArrayList<>();
6    // The number of numbers to use in each combination
7    private int combinationLength;
8
9    // The public method that initiates the combination search
10    public List<List<Integer>> combinationSum3(int k, int n) {
11        this.combinationLength = k;
12        searchCombinations(1, n);
13        return combinations;
14    }
15
16    // Helper method to perform depth-first search for combinations
17    private void searchCombinations(int start, int remainingSum) {
18        // If remaining sum is zero and the current combination's size is k
19        if (remainingSum == 0) {
20            if (currentCombination.size() == combinationLength) {
21                // Found a valid combination, add a copy to the result list
22                combinations.add(new ArrayList<>(currentCombination));
23            }
24            return; // Backtrack
25        }
26        // If the current number exceeds 9, the remaining sum, or if we have enough numbers in the current combination
27        if (start > 9 || start > remainingSum || currentCombination.size() >= combinationLength) {
28            return; // Cannot find a valid combination from here, backtrack
29        }
30        // Include 'start' in the current combination
31        currentCombination.add(start);
32        // Continue to the next number with the updated remaining sum
33        searchCombinations(start + 1, remainingSum - start);
34        // Exclude 'start' from the current combination (backtrack)
35        currentCombination.remove(currentCombination.size() - 1); 
36        // Continue to the next number without including 'start'
37        searchCombinations(start + 1, remainingSum);
38    }
39}
40

1class Solution {
2public:
3    vector<vector<int>> combinationSum3(int k, int n) {
4        // ans stores all the unique combinations
5        vector<vector<int>> ans;
6      
7        // temp stores the current combination
8        vector<int> temp;
9      
10        // Define DFS function to find combinations
11        function<void(int, int)> dfs = [&](int start, int sum) {
12            // If the remaining sum is zero and the current combination has k numbers, add to answer
13            if (sum == 0 && temp.size() == k) {
14                ans.emplace_back(temp);
15                return;
16            }
17            // Prune the search space if the current number exceeds the needed sum, or the size of the
18            // combination exceeds or if the current number is greater than 9
19            if (start > 9 || start > sum || temp.size() >= k) {
20                return;
21            }
22            // Include the current number and move to the next number
23            temp.emplace_back(start);
24            dfs(start + 1, sum - start);
25          
26            // Exclude the current number and move to the next number
27            temp.pop_back();
28            dfs(start + 1, sum);
29        };
30      
31        // Begin DFS with number 1 and target sum n
32        dfs(1, n);
33        return ans;
34    }
35};
36

1function combinationSum3(setSize: number, targetSum: number): number[][] {
2    // Initialize a list to hold all the unique combinations
3    const combinations: number[][] = [];
4    // Temporary list to hold the current combination
5    const tempCombination: number[] = [];
6
7    // Define a depth-first search function to explore possible combinations
8    const depthFirstSearch = (start: number, remainingSum: number) => {
9        // If remaining sum is 0 and combination size equals the target set size, we found a valid combination
10        if (remainingSum === 0 && tempCombination.length === setSize) {
11            // Add a copy of the valid combination to the list of combinations
12            combinations.push([...tempCombination]);
13            return;
14        }
15
16        // Termination condition: if the start number is greater than 9, 
17        // greater than the remaining sum needed, or the combination size exceeds the set size
18        if (start > 9 || start > remainingSum || tempCombination.length > setSize) {
19            return;
20        }
21
22        // Include the current number in the combination and move to the next number
23        tempCombination.push(start);
24        depthFirstSearch(start + 1, remainingSum - start);
25
26        // Exclude the current number from the combination and move to the next number
27        tempCombination.pop();
28        depthFirstSearch(start + 1, remainingSum);
29    };
30
31    // Start the depth-first search with 1 as the starting number and the target sum
32    depthFirstSearch(1, targetSum);
33
34    // Return all found combinations
35    return combinations;
36}
37

Time and Space Complexity

The given Python code defines a method combinationSum3 that finds all possible combinations of k different numbers that add up to a number n, where each number is from 1 to 9 (inclusive) and each combination is unique.

Time Complexity

The time complexity of this function can be analyzed by looking at the recursive dfs calls. Each call to dfs potentially makes two further calls, corresponding to including the current number i or excluding it. We can view this as a binary tree of decisions, where at each step, we decide whether to include a number in our current combination (t.append(i)) or not (dfs(i + 1, s)).

Each number between 1 and 9 is considered exactly once in the context of a particular combination, and there are 9 choices at the first call, 8 at the second, and so forth. However, the depth of our recursion is limited by k (the size of each combination) and the fact that we do not consider subsequent numbers once we reach a sum greater than n or a combination length equal to k.

Therefore, the time complexity is O(9! / (9 - k)!) in the worst case (when n is large enough to allow all combinations of k numbers). Note that since k <= 9, this time complexity remains within a polynomial bound with respect to 9 (the number of different numbers we can pick).

Space Complexity

The space complexity is determined by the space needed for the recursive call stack and the space used to store the combinations. In the worst case, the recursion can go as deep as k, as we stop further recursion when the length of the temporary list t reaches k. Therefore the recursion call stack will contribute O(k).

The space for storing all the combinations also needs to be considered. We have a list of lists to store the valid combinations, and, at most, each combination contains k elements. In the worst case, the number of combinations stored will also be bounded by the total number of combinations of k numbers out of 9, which is O(9! / (k!(9 - k)!)) (this is the binomial coefficient representing the number of ways to choose k distinct integers from a set of 9).

However, because these combinations are part of the output, we often do not count this as extra space in terms of space complexity analysis (since the space is required to represent the output). Thus the space complexity is usually considered to be O(k), which accounts only for the recursion depth and not the output storage.

Combining both the recursion call stack and the output storage, and if we were to include the output as part of the space complexity, our total space complexity would be O(9! / (k!(9 - k)!) + k).

The complexities provided assume that k and n are fixed and do not grow with the input size since they are parameters and not part of the input. Therefore, we should clarify that this complexity analysis is specific to this problem and not generally applicable to variations where k or n might not be bounded by small constants.

Learn more about how to find time and space complexity quickly using problem constraints.

Discover Your Strengths and Weaknesses: Take Our 2-Minute Quiz to Tailor Your Study Plan:

Question 1 out of 10

What's the output of running the following function using input 56?

1KEYBOARD = {
2    '2': 'abc',
3    '3': 'def',
4    '4': 'ghi',
5    '5': 'jkl',
6    '6': 'mno',
7    '7': 'pqrs',
8    '8': 'tuv',
9    '9': 'wxyz',
10}
11
12def letter_combinations_of_phone_number(digits):
13    def dfs(path, res):
14        if len(path) == len(digits):
15            res.append(''.join(path))
16            return
17
18        next_number = digits[len(path)]
19        for letter in KEYBOARD[next_number]:
20            path.append(letter)
21            dfs(path, res)
22            path.pop()
23
24    res = []
25    dfs([], res)
26    return res
27

1private static final Map<Character, char[]> KEYBOARD = Map.of(
2    '2', "abc".toCharArray(),
3    '3', "def".toCharArray(),
4    '4', "ghi".toCharArray(),
5    '5', "jkl".toCharArray(),
6    '6', "mno".toCharArray(),
7    '7', "pqrs".toCharArray(),
8    '8', "tuv".toCharArray(),
9    '9', "wxyz".toCharArray()
10);
11
12public static List<String> letterCombinationsOfPhoneNumber(String digits) {
13    List<String> res = new ArrayList<>();
14    dfs(new StringBuilder(), res, digits.toCharArray());
15    return res;
16}
17
18private static void dfs(StringBuilder path, List<String> res, char[] digits) {
19    if (path.length() == digits.length) {
20        res.add(path.toString());
21        return;
22    }
23    char next_digit = digits[path.length()];
24    for (char letter : KEYBOARD.get(next_digit)) {
25        path.append(letter);
26        dfs(path, res, digits);
27        path.deleteCharAt(path.length() - 1);
28    }
29}
30

1const KEYBOARD = {
2    '2': 'abc',
3    '3': 'def',
4    '4': 'ghi',
5    '5': 'jkl',
6    '6': 'mno',
7    '7': 'pqrs',
8    '8': 'tuv',
9    '9': 'wxyz',
10}
11
12function letter_combinations_of_phone_number(digits) {
13    let res = [];
14    dfs(digits, [], res);
15    return res;
16}
17
18function dfs(digits, path, res) {
19    if (path.length === digits.length) {
20        res.push(path.join(''));
21        return;
22    }
23    let next_number = digits.charAt(path.length);
24    for (let letter of KEYBOARD[next_number]) {
25        path.push(letter);
26        dfs(digits, path, res);
27        path.pop();
28    }
29}
30

["jk", "mno"]

["jm", "kn", "lo"]

["jklmnp"]

["jm","jn","jo","km","kn","ko","lm","ln","lo"]

I don’t know