1. Problem Summary

You are given two integers:

• k — the required number of elements in the combination
• n — the target sum

Your task is to return all unique combinations of exactly k distinct numbers where:

• The numbers are chosen from the range 1 to 9
• The numbers must be strictly increasing (no repetition)
• The sum of the selected numbers must equal n

The result must contain only valid combinations, and the order of combinations does not matter.

Example interpretation:
If k = 3 and n = 7, one valid combination is [1, 2, 4] because:

• It has 3 numbers
• They are distinct
• They lie between 1 and 9
• They sum to 7

---

2. Key Insights

Only digits 1 to 9 are available

So there are at most 9 numbers to consider.

No repetition allowed

Numbers must be used at most once.

Combinations must be strictly increasing

This prevents duplicates automatically.

Backtracking fits perfectly

At each step:

• choose a number
• reduce remaining sum
• reduce remaining count
• continue forward, not backward

Early pruning improves performance

Stop exploring when:

• sum becomes negative
• too many numbers are picked
• too few numbers left to reach k

---

3. Approach

Backtracking Strategy

We maintain:

• a list current storing chosen numbers so far
• a pointer start telling which number to try next
• remaining sum remainingSum
• remaining count remainingCount

Steps:

1. If remainingSum == 0 and remainingCount == 0, record the current combination.
2. If remainingSum < 0 or remainingCount < 0, stop exploring that path.
3. Loop from current number start to 9:
   • add number to current list
   • recurse with updated parameters
   • remove number (backtrack)

This systematically explores all valid increasing selections.

---

4. Time and Space Complexity

Time Complexity: O(Combination Count)

Upper bound roughly:

C(9, k)

Because combinations come from 9 available numbers.

Space Complexity: O(k)

Maximum recursion depth equals the size of each combination.

---

5. Java Solution

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

class Solution {
    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> current,
                           int remainingCount, int remainingSum, int start) {

        if (remainingSum == 0 && remainingCount == 0) {
            result.add(new ArrayList<>(current));
            return;
        }

        if (remainingSum < 0 || remainingCount < 0) {
            return;
        }

        for (int num = start; num <= 9; num++) {
            current.add(num);
            backtrack(result, current, remainingCount - 1, remainingSum - num, num + 1);
            current.remove(current.size() - 1);
        }
    }
}

---

6. Dry Run Example

Input:

k = 3, n = 7

Goal:
Find combinations of 3 numbers from 1–9 that sum to 7.

Exploration steps:

Start: current = [], remainingCount = 3, remainingSum = 7, start = 1

Try 1:

• current = [1], remainingCount = 2, remainingSum = 6, start = 2

Try 2:

• current = [1,2], remainingCount = 1, remainingSum = 4, start = 3

Try 3:

• current = [1,2,3], remainingCount = 0, remainingSum = 1 → not valid

Backtrack

Try 4:

• current = [1,2,4], remainingCount = 0, remainingSum = 0 → VALID

Add: [1,2,4]

Backtrack through 5–9, all exceed sum or count

Try 3 as first element:

• current = [3], remainingSum = 4, remainingCount =2
  Explores but cannot reach sum 7

Try 4 as first element:

• current = [4], remainingSum = 3, remainingCount =2
  Fails eventually

Try 5+ as first picks:
Too large to form sum 7 in 3 numbers

Final output:

[[1, 2, 4]]