The article directories

      • Subset problem (all nodes) : 78. Subset, you don’t need to prune and de-weight the results
      • Subset problem (all nodes) : problem 90. Subset II (sets without duplicates, same as the last combination problem, elements are not allowed to be reused, plus the used array)
      • Subsequence problem (all nodes) : 491. Increasing subsequence (subsequence problem and subset problem are two different things)

Subset problem (all nodes) : 78. Subset, you don’t need to prune and de-weight the results

Given an array of integers with no repeating elements, nums returns all possible subsets (power sets) of the array.

Note: The solution set cannot contain duplicate subsets (explicitly given by the topic)

Example: the input: nums = [1, 2, 3] output: [[3], [1], [2], [1, 2, 3], [1, 3], [2, 3], [1, 2], []]

Train of thought seek subset problem and backtracking algorithm: seek combination problem! And backtracking algorithms: segmentation problems! It’s different again.

If the subset problem, combination problem, segmentation problem are abstract for a tree, “then combination problem and segmentation problem are to collect the tree leaf nodes, and subset problem is to find all nodes of the tree!”

In fact, subset is also a combinatorial problem, because the set is unordered, subset {1,2} and subset {2,1} are the same.

“So since it’s unordered, the elements won’t be fetched again, so when writing a backtracking algorithm, for should start at startIndex, not 0!”

When can “for” start at zero?

When you do permutation, you start at 0, because sets are ordered, {1, 2} and {2, 1} are two sets, and permutation is something we’ll talk about in a later article.

class Solution {
    List<List<Integer>> result = new ArrayList<>();
    List<Integer> path=new ArrayList<>();
    public void backtracking(int[] nums,int startIndex){
        result.add(new ArrayList<>(path));
        if (startIndex >= nums.length){
            return;
        }
        for(int i=startIndex; i<nums.length; I ++){// startIndex = 0, path.add(nums[I]); Backtracking (nums, I +1); path.remove(path.size()-1); } } public List<List<Integer>> subsets(int[] nums) { backtracking(nums,0); // Every time we start, we start at 0returnresult; }}Copy the code

Subset problem (all nodes) : problem 90. Subset II (sets without duplicates, same as the last combination problem, elements are not allowed to be reused, plus the used array)

Given an integer array nums that may contain repeating elements, return all possible subsets (power sets) of that array.

Note: The solution set cannot contain duplicate subsets (explicitly given by the topic)

Example: input, output,2,2 [1] : [[2], [1],,2,2 [1], [2], [1, 2], []]

“To reveal the plot, the arrangement problem that will be explained later is also the same method, so it is very important to understand the ‘tree layer weight’ and ‘branch weight’.”

Use [1, 2, 2] in the example, as shown :(” note that de-replay requires sorting the collection first “)

class Solution {
    List<List<Integer>> result = new ArrayList<>();
    List<Integer> path=new ArrayList<>();
    public void backtracking(int[] nums,int startIndex,boolean[] used){
        result.add(new ArrayList<>(path));
        if(startIndex >= nums.length){// Finally this is the end conditionreturn;
        }
        for(int i=startIndex; i<nums.length; I++){// from startIndex to nums.length-1, startIndex is 0 on the first entry, then +1 each timeif (i>0 && nums[i]==nums[i-1] && used[i-1]==false)
                continue; Add (nums[I]); // Add the element used[I]=true;
            backtracking(nums,i+1,used);
            path.remove(path.size()-1);
            used[i]=false;
        }
    }
    public List<List<Integer>> subsetsWithDup(int[] nums) {
        boolean[] used=new boolean[nums.length];
        for(int i=0; i<used.length; i++) used[i]=false; Arrays.sort(nums); Backtracking (nums,0,used); // Every time we start, we start at 0returnresult; }}Copy the code

Core: for as a result, the elements within the same combination can be repeated, how to repeat all right, but two sons and a combination cannot be the same Each element can be used only once in the combination (a combination of mathematical properties, topic clear given conditions), and the result can’t contain the same child composite (topic clear a given output requirements, a combination is the number of elements in a disorderly) : After the large combination is arranged in order, the same element can only be used once in the same tree layer and appear twice, and the resulting sub-combination will be repeated. Each element in a large set can be used only once, and the result cannot contain the same subset (the number of elements in the subset is unordered) : Once a large set is sorted, the same elements can only be used once, and appear twice, resulting in repeated subsets.

Each element in a large sequence can be used only once, and the result cannot contain the same subsequence (if) : After the large sequence is given (can not be sorted), the same element in the same tree layer can only be used once, appear twice, the resulting subsequence will have repeated. Also, the number of elements in the subsequence is increasing, so we need to prune if. So two pruning

Subsequence problem (all nodes) : 491. Increasing subsequence (subsequence problem and subset problem are two different things)

The subsequence problem is different from the subset problem

  1. The first pruning if is different, i.e., the reduplication logic is different. The subset needs to be sorted before execution, and the subsequence does not need to be sorted before execution.
  2. The second clipping if is different, and the subsequence has one more clipping if, that is, the current element cannot be greater than the last element of the subsequence.

Given an array of integers, your task is to find all the increasing subsequences of the array. The increasing subsequences are at least 2 in length.

Example:

Input: [4, 6, 7, 7] output: [[4, 6], [4, 7], [4, 6, 7], [4, 6, 7, 7], [6, 7], [6, 7, 7], [7, 7], [4,7,7]]

Idea: in this case, we can not sort the original array. The sorted array is an autoincrement subsequence.

class Solution { List<List<Integer>> result = new ArrayList<>(); List<Integer> path = new ArrayList<>(); Public void backtracking(int[] nums,int startIndex){public void backtracking(int[] nums,int startIndex){if(path.size() > 1){ result.add(new ArrayList<>(path)); // This is the end condition, also successful end condition, because there is no failure and end condition, failure condition is result [], initialization result // do not add herereturnTo get the node out of the tree // addreturnWe always get a subsequence} Set of two elementsset=new HashSet(); // setThe built-in de-weight function de-weights during recursion, not inforIn the loop go heavy // infor// start nums.length-1 from startIndex, I cannot start at 0, otherwise I +1 is meaninglessfor(int i=startIndex; i<nums.length; I++){// first prune, cannot add less thanif(! path.isEmpty() && nums[i]<path.get(path.size()-1))continue; // The second pruning can not contain the same tree usedif (set.contains(nums[i])==true) / /setThe definition of must be inforOutside of the loopcontinue;
            path.add(nums[i]);
            set.add(nums[i]);
            backtracking(nums,i+1);
            path.remove(path.size()-1);
        }
    }
    public List<List<Integer>> findSubsequences(int[] nums) {
        backtracking(nums,0);
        returnresult; }}Copy the code

Why not add return to the end condition; If (path.size() > 1), return to the previous function and execute path.remove(path.size()-1); You can always print a subsequence of two elements without a return; Remove (path.size()-1) if startIndex == nums.length; Core: can’t add return; If (path.size() > 1), return (path.size() > 1)