Welcome to Subscribe On Youtube

216. Combination Sum III

Description

Find all valid combinations of k numbers that sum up to n such that the following conditions are true:

  • Only numbers 1 through 9 are used.
  • Each number is used at most once.

Return a list of all possible valid combinations. The list must not contain the same combination twice, and the combinations may be returned in any order.

 

Example 1:

Input: k = 3, n = 7
Output: [[1,2,4]]
Explanation:
1 + 2 + 4 = 7
There are no other valid combinations.

Example 2:

Input: k = 3, n = 9
Output: [[1,2,6],[1,3,5],[2,3,4]]
Explanation:
1 + 2 + 6 = 9
1 + 3 + 5 = 9
2 + 3 + 4 = 9
There are no other valid combinations.

Example 3:

Input: k = 4, n = 1
Output: []
Explanation: There are no valid combinations.
Using 4 different numbers in the range [1,9], the smallest sum we can get is 1+2+3+4 = 10 and since 10 > 1, there are no valid combination.

 

Constraints:

  • 2 <= k <= 9
  • 1 <= n <= 60

Solutions

DFS.

This is a typical backtracking problem that explores all possible combinations to find those that meet the criteria.

Function Signature

def combinationSum3(self, k: int, n: int) -> List[List[int]]:
  • The function combinationSum3 takes two arguments: k, the number of digits in each combination, and n, the target sum.
  • It returns a list of lists, where each inner list is a combination of k digits that add up to n.

The dfs (Depth-First Search) Helper Function

def dfs(start, s, t): # s: sum, t: list
  • dfs is a recursive helper function defined within combinationSum3. It is used to perform a depth-first search to explore all possible combinations.
  • start: The starting point for the current exploration, ensuring that only numbers greater than start are considered to avoid repeats and maintain uniqueness.
  • s: The current sum of the numbers in the temporary list t.
  • t: A temporary list that stores the current combination being explored.

The Recursive Exploration

  • The recursion starts with dfs(1, 0, []), meaning the search begins with the number 1, the current sum as 0, and an empty list for the combination.
  • The base case of the recursion checks if the current sum s exceeds n or if the length of the temporary list t exceeds k. If either condition is true, the recursion returns, as the current path cannot yield a valid combination.
  • Another base case checks if s == n and len(t) == k. If both conditions are met, a valid combination is found, and a copy of t is added to the answer list ans. The copy is used because t is modified in subsequent steps.
  • The recursive step iterates from start to 9 (inclusive of 1 and exclusive of 10 because we’re dealing with digits). For each number i in this range, it is added to t, and dfs is called recursively with the updated parameters: the next starting number (i + 1), the new sum (s + i), and the updated temporary list t. After the recursive call returns, t.pop() is called to backtrack, removing the last number added to t and exploring other possibilities.

Collecting and Returning the Answer

  • ans is initialized as an empty list. It collects all valid combinations found during the depth-first search.
  • After exploring all possibilities through recursive backtracking, ans is returned, containing all combinations of k numbers that sum to n.
  • class Solution {
    private List<List<Integer>> ans = new ArrayList<>();
    private List<Integer> t = new ArrayList<>();
    private int k;

    public List<List<Integer>> combinationSum3(int k, int n) {
        this.k = k;
        dfs(1, n);
        return ans;
    }

    private void dfs(int i, int s) {
        if (s == 0) {
            if (t.size() == k) {
                ans.add(new ArrayList<>(t));
            }
            return;
        }
        if (i > 9 || i > s || t.size() >= k) {
            return;
        }
        t.add(i);
        dfs(i + 1, s - i);
        t.remove(t.size() - 1);
        dfs(i + 1, s);
    }
}

  • class Solution {
public:
    vector<vector<int>> combinationSum3(int k, int n) {
        vector<vector<int>> ans;
        vector<int> t;
        function<void(int, int)> dfs = [&](int i, int s) {
            if (s == 0) {
                if (t.size() == k) {
                    ans.emplace_back(t);
                }
                return;
            }
            if (i > 9 || i > s || t.size() >= k) {
                return;
            }
            t.emplace_back(i);
            dfs(i + 1, s - i);
            t.pop_back();
            dfs(i + 1, s);
        };
        dfs(1, n);
        return ans;
    }
};

  • class Solution:
    def combinationSum3(self, k: int, n: int) -> List[List[int]]:
        def dfs(start, s, t): # s: sum, t: list
            if s > n or len(t) > k:
                return
            if s == n and len(t) == k:
                ans.append(t.copy())
                return

            for i in range(start, 10):
                t.append(i)
                dfs(i + 1, s + i, t)
                t.pop()

        ans = []
        dfs(1, 0, [])
        return ans


  • func combinationSum3(k int, n int) (ans [][]int) {
	t := []int{}
	var dfs func(i, s int)
	dfs = func(i, s int) {
		if s == 0 {
			if len(t) == k {
				ans = append(ans, slices.Clone(t))
			}
			return
		}
		if i > 9 || i > s || len(t) >= k {
			return
		}
		t = append(t, i)
		dfs(i+1, s-i)
		t = t[:len(t)-1]
		dfs(i+1, s)
	}
	dfs(1, n)
	return
}

  • function combinationSum3(k: number, n: number): number[][] {
    const ans: number[][] = [];
    const t: number[] = [];
    const dfs = (i: number, s: number) => {
        if (s === 0) {
            if (t.length === k) {
                ans.push(t.slice());
            }
            return;
        }
        if (i > 9 || i > s || t.length > k) {
            return;
        }
        t.push(i);
        dfs(i + 1, s - i);
        t.pop();
        dfs(i + 1, s);
    };
    dfs(1, n);
    return ans;
}


  • public class Solution {
    private List<IList<int>> ans = new List<IList<int>>();
    private List<int> t = new List<int>();
    private int k;

    public IList<IList<int>> CombinationSum3(int k, int n) {
        this.k = k;
        dfs(1, n);
        return ans;
    }

    private void dfs(int i, int s) {
        if (s == 0) {
            if (t.Count == k) {
                ans.Add(new List<int>(t));
            }
            return;
        }
        if (i > 9 || i > s || t.Count >= k) {
            return;
        }
        t.Add(i);
        dfs(i + 1, s - i);
        t.RemoveAt(t.Count - 1);
        dfs(i + 1, s);
    }
}

  • impl Solution {
    #[allow(dead_code)]
    pub fn combination_sum3(k: i32, n: i32) -> Vec<Vec<i32>> {
        let mut ret = Vec::new();
        let mut candidates = (1..=9).collect();
        let mut cur_vec = Vec::new();
        Self::dfs(n, k, 0, 0, &mut cur_vec, &mut candidates, &mut ret);
        ret
    }

    #[allow(dead_code)]
    fn dfs(
        target: i32,
        length: i32,
        cur_index: usize,
        cur_sum: i32,
        cur_vec: &mut Vec<i32>,
        candidates: &Vec<i32>,
        ans: &mut Vec<Vec<i32>>
    ) {
        if cur_sum > target || cur_vec.len() > (length as usize) {
            // No answer for this
            return;
        }
        if cur_sum == target && cur_vec.len() == (length as usize) {
            // We get an answer
            ans.push(cur_vec.clone());
            return;
        }
        for i in cur_index..candidates.len() {
            cur_vec.push(candidates[i]);
            Self::dfs(target, length, i + 1, cur_sum + candidates[i], cur_vec, candidates, ans);
            cur_vec.pop().unwrap();
        }
    }
}


  • function combinationSum3(k, n) {
    const ans = [];
    const t = [];
    const dfs = (i, s) => {
        if (s === 0) {
            if (t.length === k) {
                ans.push(t.slice());
            }
            return;
        }
        if (i > 9 || i > s || t.length >= k) {
            return;
        }
        t.push(i);
        dfs(i + 1, s - i);
        t.pop();
        dfs(i + 1, s);
    };
    dfs(1, n);
    return ans;
}

All Problems

All Solutions