algoadvance

Leetcode 216. Combination Sum III

Problem Statement

The problem “216. Combination Sum III” from LeetCode requires you to 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.

Clarifying Questions

  1. What are the constraints on the values of k and n?
    • The constraints are 1 ≤ k ≤ 9 and 1 ≤ n ≤ 60.
  2. Can a number be used more than once in the combination?
    • No, each number from 1 to 9 can be used at most once in each combination.
  3. Is the order of numbers in the combination relevant?
    • No, the combinations themselves should be unique, but the order does not matter.
  4. Should the function return the combinations in a specific order?
    • The problem does not specify an order, so we can return combinations in any order.

Strategy

We can use a backtracking approach to solve this problem:

  1. Backtracking:
    • We need to explore all possible combinations using numbers from 1 to 9.
    • We start from the smallest number and add it to our current combination if it doesn’t exceed our target n.
    • Recursively call the function to find the next number.
    • If the current combination’s length is k and the sum is n, add it to the result list.
    • Backtrack by removing the last added number and try the next possible number.

Code

Here’s the code implementing the above strategy:

import java.util.ArrayList;
import java.util.List;

public class CombinationSumIII {
    public List<List<Integer>> combinationSum3(int k, int n) {
        List<List<Integer>> result = new ArrayList<>();
        backtrack(result, new ArrayList<>(), k, n, 1);
        return result;
    }

    private void backtrack(List<List<Integer>> result, List<Integer> combination, int k, int n, int start) {
        if (combination.size() == k && n == 0) {
            result.add(new ArrayList<>(combination));
            return;
        }

        for (int i = start; i <= 9; i++) {
            if (i > n) {
                break;
            }
            combination.add(i);
            backtrack(result, combination, k, n - i, i + 1);
            combination.remove(combination.size() - 1);
        }
    }

    public static void main(String[] args) {
        CombinationSumIII cs3 = new CombinationSumIII();
        System.out.println(cs3.combinationSum3(3, 7)); // Output: [[1, 2, 4]]
        System.out.println(cs3.combinationSum3(3, 9)); // Output: [[1, 2, 6], [1, 3, 5], [2, 3, 4]]
    }
}

Time Complexity

The time complexity of this solution involves exploring all the combinations of numbers from 1 to 9:

Therefore, the time complexity is approximately (O(2^n)), specifically considering the small constant limits (numbers 1 to 9) and combinations within bounds of 9.

Space Complexity

The space complexity is mainly due to:

Hence, the space complexity is (O(k)) for the recursive call stack in the worst case, plus the space required to store valid combinations, which in the worst scenario is (O(C(9, k))).

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