Solving combinational problems with Backtracking instead of Brute force: N recursions instead of n for loops (essence)

The article directories

• • • Problem 77. Combination
    • Problem 216. Sum of combinations III
    • 39. Sum of combinations (large combinations that do not contain the same elements, but each element can be reused + unlimited k, unlimited number of loops or recursions)
    • Number 40. Sum of combinations II (large combinations containing the same elements, but each element can only be used once + unlimited k, unlimited number of loops or recursions)

Problem 77. Combination

class Solution {
    List<List<Integer>> result = new ArrayList<>();
    List<Integer> path = new LinkedList<>();
    public  void backtracking(int n,int k,int startIndex){
        if(path.size() == k){ result.add(new ArrayList<>(path.subList(0,k))); // If path is deleted to result, result is not deletedreturn;
        }
        for(int i=startIndex; i<=n; i++){ path.add(i); backtracking(n,k,i+1); Path.remove (path.size()-1); // Remove (path.size()-1); Public List<List<Integer>> combine(int n, int k) {backtracking(n,k,1); backtracking(n,k,1); // result is a class variable and has been modified so there is no need to accept itreturnresult; }}Copy the code

< span style = “max-width: 100%; clear: both; min-height: 100%; I <=n (I <=n); I <=n (I <=n); I <=n (I <=n)

Pruning operation

1. Number of selected elements: path.size();
2. K-path.size ();
3. At most, the traversal in set N starts at this starting position: n – (k-path.size ()) + 1

Why do we have a plus one? Because including the starting position, we have to be a left closed set.

For example, n = 4, k = 3, the selected element is 0 (path.size is 0), n – (k-0) + 1 = 4 – (3-0) + 1 = 2.

It is reasonable to search from 2, and can be combinations [2, 3, 4].

If you don’t understand this, I suggest you use an example to see if you want to +1.

So the optimized for loop is:

for(int i = startIndex; i <= n - (k - path.size()) + 1; I ++) // I is the starting position of the searchCopy the code

Pruning (path.size pruning)

class Solution {
    List<List<Integer>> result = new ArrayList<>();
    List<Integer> path = new LinkedList<>();
    public  void backtracking(int n,int k,int startIndex){
        if(path.size() == k){ result.add(new ArrayList<>(path.subList(0,k))); // If path is deleted to result, result is not deletedreturn;
        }
        for(int i=startIndex; i<=n-(k-path.size())+1; i++){ path.add(i); backtracking(n,k,i+1); Path.remove (path.size()-1); // Remove (path.size()-1); Public List<List<Integer>> combine(int n, int k) {backtracking(n,k,1); backtracking(n,k,1); // result is a class variable and has been modified so there is no need to accept itreturnresult; }}Copy the code

Problem 216. Sum of combinations III

class Solution {
    List<List<Integer>> result = new ArrayList<>();
     List<Integer> path = new LinkedList<>();
    public   void backtracking(int n,int k,int sum,int startIndex){
        if (path.size() == k ){
            if(sum==n){
                result.add(new ArrayList<>(path.subList(0,k)));  // 这样，path删除到，result不会删除   找到了一组合适的，添加到result中
            }
            return; // When path.size reaches k, the sum cannot be addedreturn; To make a recursive child call, go to path.remove}for(int i=startIndex; i<=9; Sum = sum + I){sum = sum + I; sum = sum + I; sum = sum + I; sum = sum + I; path.add(i); backtracking(n,k,sum,i+1); Sum =sum- I; sum=sum- I; sum=sum- I; sum=sum- I; path.remove(path.size()-1); // Because path is placed in result, }} public List<List<Integer>> combinationSum3(int k, int n) {backtracking(n,k,0,1); // result is not accepted, the class variable has been modifiedreturnresult; }}Copy the code

class Solution {
    List<List<Integer>> result = new ArrayList<>();
     List<Integer> path = new LinkedList<>();
    public   void backtracking(int n,int k,int sum,int startIndex){
        if(sum > n) //return;
        if (path.size() == k ){
            if(sum==n){
                result.add(new ArrayList<>(path.subList(0,k)));  // 这样，path删除到，result不会删除   找到了一组合适的，添加到result中
            }
            return; // When path.size reaches k, the sum cannot be addedreturn; For recursive child calls, prune path.remove} // path.sizefor(int i=startIndex; i<=9-(k-path.size())+1; Sum = sum + I){sum = sum + I; sum = sum + I; sum = sum + I; sum = sum + I; path.add(i); backtracking(n,k,sum,i+1); Sum =sum- I; sum=sum- I; sum=sum- I; sum=sum- I; path.remove(path.size()-1); // Because path is placed in result, }} public List<List<Integer>> combinationSum3(int k, int n) {backtracking(n,k,0,1); // result is not accepted, the class variable has been modifiedreturnresult; }}Copy the code

39. Sum of combinations (large combinations that do not contain the same elements, but each element can be reused + unlimited k, unlimited number of loops or recursions)

Given an array of no duplicate elements and a target number, find all combinations of the candidates that make the numeric sum target.

The numbers in the candidates can be selected repeatedly without limit.

Key: The numbers in the candidates can be selected indefinitely, and each number has no limit on the number of times

First, the number of elements in each subcombination of k is uncertain. However, subcombinations are not allowed to repeat (combinations rather than ordering, starting from I +1 each time). Number two, the big combination, where do you choose the candidates and number three, target is n, the candidates are there

The number of elements in each subgroup is uncertain, so there is no need to determine the number of elements in path.size or prune based on path.size. The e elements in the candidates are not repeated, but they can be used repeatedly.

The code is as follows:

class Solution { List<List<Integer>> result = new ArrayList<>(); List<Integer> path=new ArrayList<>(); // The first two are arguments to the Solution function and cannot be changed into class variables; StartIndex is a variable that changes every time, so you can't use it as a class variable, although you don't change it in this problem, you can use it as a class variable, Public void backtracking(int[],int target,int sum,int startIndex){if (sum > target)
          return;
      ifResult. add(new ArrayList<>(path)); // If path is deleted, result is not deletedreturn; } // startIndex asforStart loop, make sure the subgroup doesn't repeat, if I =0, it starts repeating, and it's stored in the Listfor(int i=startIndex; i<candidates.length; Sum = sum + argument [I]; // The candidate just gives data path.add(argument [I]); // Add a backtracking element to the end (candidates,target,sum, I); StartIndex = I startIndex sum = sum - argument [I]; path.remove(path.size()-1); }} public List<List<Integer>> combinationSum(int[] letters, {int target) backtracking (candidates, target, 0, 0); // Since the given large combination is an array, we can go from 0 to n-1 if given an n numberreturnresult; }}Copy the code

The candidates must run the campaign and the candidates must run the campaign. The candidates must run the campaign and the candidates must run the campaign.

For a large number of candidates, the “for” loop runs from 0 to n, so the “for” loop runs from 0 to n, so the “for” loop runs from 0 to n, so the “for” loop runs from 0 to n.

Number 40. Sum of combinations II (large combinations containing the same elements, but each element can only be used once + unlimited k, unlimited number of loops or recursions)

class Solution { List<List<Integer>> result = new ArrayList<>(); List<Integer> path=new ArrayList<>(); // The first two are arguments to the Solution function and cannot be changed into class variables; StartIndex is a variable that changes every time, so you can't use it as a class variable, although you don't change it in this problem, you can use it as a class variable, Public void backtracking(int[] candidates, int target,int sum,int startIndex, Boolean [] used){if (sum > target)
            return;
        ifResult. add(new ArrayList<>(path)); // If path is deleted, result is not deletedreturn;
        }
        for(int i=startIndex; i<candidates.length; I++){// since the given large combination is an array, it goes from 0 to n-1if (i>0 && used[i-1]==false// If i-1 is not used, I will not be used. If i-1 is used, I will be usedcontinue; Sum = sum + sum [I]; sum = sum + sum [I]; sum = sum + sum [I]; // The candidate just gives data path.add(argument [I]); // Add an element used[I]= to the endtrue; // The I sign is already used backtracking(candidates,target,sum, I +1,used); used[i]=false; // This sentence is the sum = sum - argument [I]; path.remove(path.size()-1); // Delete the last element, }} public List<List<Integer>> combinationSum2(int[] script, int target) { Arrays.sort(candidates); Boolean [] used=new Boolean [candidates.length];for(int i=0; i<used.length; i++) used[i]=false; // All initialized tofalseHas said that it had not using backtracking (candidates, target, 0, 0, 2); // Since the given large combination is an array, we can go from 0 to n-1 if given an n numberreturnresult; }}Copy the code