Topic describes

This is 216 on LeetCode. Combination sum III, Medium difficulty.

Find all the combinations of k numbers that add up to n. Only positive integers from 1 to 9 are allowed in a combination, and there are no duplicate digits in each combination.

Description:

  • All numbers are positive integers.
  • The solution set cannot contain repeated combinations.

Example 1:

Input: k = 3, n = 7 output: [[1,2,4]]Copy the code

Example 2:

Input: k = 3, n = 9 output: [[1,2,6], [1,3,5], [2,3,4]]Copy the code

DFS + backtracking method

As for the problem of combination sum, we have completed 39. Combination sum and 40. Combination sum II is two problems.

Except the first two problems just give us an array and let us choose from the array.

The number ranges from 1 to 9.

All three problems can be solved using the same idea.

Let’s reinforce how to quickly determine if a question should be searched using DFS + backtracking.

In general, you can think about it in two ways:

  • 1. Find all options, not the number of options. Since we’re looking at all scenarios, there can’t be any particular optimization, so we just have to enumerate. The possible solutions include dynamic programming, mnemonic search and DFS + backtracking.

  • 2. Usually the data range is not very large, only dozens. For dynamic programming or mnemonic search problems, the general data range can be 10510^5105 to 10710^7107 due to their low repetition/non-repetition enumeration, while DFS + backtracking is usually limited to 30.

So this is going to be up to 30, and it’s going to be all of them. Therefore, we use DFS + backtracking to solve:

class Solution {
    int n, k;
    public List<List<Integer>> combinationSum3(int _k, int _n) {
        n = _n;
        k = _k;

        List<List<Integer>> ans = new ArrayList<>();
        List<Integer> cur = new ArrayList<>();
        dfs(1, ans, cur, 0);
        return ans;
    }
    /** * u: the current number traversed * ans: the final result set * cur: the current result set * sum: the total of the current result set */
    void dfs(int u, List<List<Integer>> ans, List<Integer> cur, int sum) {
        if (sum == n && cur.size() == k) {
            ans.add(new ArrayList<>(cur));
            return;
        }
        if (u == 10 || sum > n || cur.size() > k) return;
        // Use the number u
        cur.add(u);
        dfs(u + 1, ans, cur, sum + u);
        // backtrace
        cur.remove(cur.size() - 1);
        // Do not use the number u
        dfs(u + 1, ans, cur, sum); }}Copy the code
  • Time complexity: DFS backtracking algorithms are usually exponentially complex (so the data range is usually up to 30). O(n∗2n)O(n * 2^n)O(n∗2n)
  • Space complexity: same as above. O(n∗2n)O(n * 2^n)O(n∗2n)

conclusion

For three days, we did three questions about the sum of combinations.

But in fact, there is no essential difference, are looking at the basic use of “backtracking algorithm”.

For such a problem that enumerates all schemes, we should first think of “backtracking algorithms”.

“Backtracking algorithm” from the definition of the algorithm, does not necessarily use DFS implementation, but usually combined with DFS, is the least difficult.

The backtracking algorithm corresponds to two sets of templates based on how many choices there are in the current decision.

  1. Each individual decision corresponds only toChoose and not chooseThere are two cases:
  • Identify the base case that ends the backtracking process
  • Traverse each location, making a decision on each location (make selection -> recurse -> Undo selection)
void dfs(Current location, path (current result), result set){
    if(Current position == end position) {result set.add (path);return; } Select the current position; DFS (next location, path (current result), result set); Unselect current location; DFS (next location, path (current result), result set); }Copy the code

40. Combination sum II…

  1. Each individual decision corresponds to multiple choices (usually corresponding to what can be chosen per decision, or how many can be chosen per decision…). :
  • Identify the base case that ends the backtracking process
  • Go through all the “choices”
  • Make a decision on the selection (make the selection -> recurse -> Undo the selection)
void dfsSelect list, path (current result), result set){
    if{result set. Add (path);return;
    }
        
    for(Select in select list) {make a selection; DFS (path ', selection list, result set); Undo selection; }}Copy the code

Examples of this template are: 17. Number combination of telephone numbers, 39. Number combination sum…

The last

This is No.216 of our “Brush through LeetCode” series, which started on 2021/01/01. As of the start date, there are 1916 questions on LeetCode, some of which have locks, so we will finish all the questions without locks first.

In this series of articles, in addition to explaining how to solve the problem, I will also present the most concise code possible. If a general solution is involved, the corresponding code template will also be used.

In order to facilitate the students to debug and submit the code on the computer, I set up the relevant warehouse: github.com/SharingSour…

In the repository, you’ll see links to the series of articles, the corresponding code for the series of articles, the LeetCode source links, and other preferred solutions.

  • This article is participating in the “Nuggets 2021 Spring Recruitment Campaign”, click to see the details of the campaign