Understand the full arrangement, combination, and subset issues in one article (collection is recommended)

Understand the full arrangement, combination, and subset issues in one article (collection is recommended)

A search on WeChat: [bigsai] Get more knowledge of liver products, thank you for having a spring breeze

Preface

Hello, everyone, I m bigsai, long time no see! In the process of brushing questions and interviews, we often encounter some permutation and combination problems, and problems such as full permutation, combination, and subset are very classic problems. This article will take you to thoroughly understand the full array!

Seek the whole arrangement?

Full permutation means: n elements take all permutations and combinations of n elements (all elements) .

Seeking a combination?

Combination is: n elements and all combinations of m elements (non-permutation) .

Seeking a subset?

Subset means: all subsets of n elements ( all possible combinations ).

In general, the total number of permutations is all elements, the difference is the order of arrangement; the combination is to select a fixed number of combinations (not looking at the permutation); the subset is to expand the combination, all possible combinations (the same or not) Consider permutation).

Of course, these three problems have similarities and slightly different. We may be exposed to more full permutations, so you can think of the combination and subset problems as extensions of the full permutation. And the problem may be whether the characters to be processed are repeated . It is also very critical and important to adopt different strategies to remove duplication! There may be many specific methods for solving each problem. The most popular methods for total permutation are the neighborhood swap method and the backtracking method , while other combination and subset problems are classic backtracking problems. And the most important and basic thing in this article is to master the non-repetitive full arrangement achieved by these two methods , and the others are based on this to transform and expand.

Permutation problem

Full arrangement, the total number of elements is the largest, the difference is the order of arrangement .

Full permutation without repetitive sequence

This question just happened to be the original question in the 46th question . You can go to a to try it after learning.

Problem Description:

Given a no repeat sequence of numbers, it returns all possible full array.

Example:

Input: [1,2,3] Output: [ [1,2,3], [1,3,2], [2,1,3], [2,3,1], [3,1,2], [3,2,1] ] Copy code

Backtracking method to achieve full arrangement without repetition

The backtracking algorithm is used to solve the search problem, and the full arrangement is also a kind of search problem. Let s review what a backtracking algorithm is:

The backtracking algorithm is actually a search trial process similar to enumeration, which is mainly to find the solution of the problem during the search trial process. When it is found that the solution condition is not met, it will "backtrack" and return and try another path.

And the whole arrangement can just use the heuristic method to enumerate all the possibilities. A sequence or set of length n. All its permutation and combination possibilities are shared

n!
Kind. The specific heuristic strategy is as follows:

  1. Select the first element from the set to be selected (a total of n cases), and mark that the element has been used and cannot be used anymore.
  2. Recurse to the next layer on the basis of step 1, find and mark an element from the remaining n-1 elements according to the method of 1, and continue to recurse downward.
  3. When all the elements are marked, the marked elements are sequentially collected and stored in the result. The current layer recursively ends and returns to the previous layer (at the same time, the marked elements of the current layer are cleared). This has been executed to the end.

If the backtracking process is roughly like this from the pseudo-code process:

recursive function: If all elements of the collection are marked: Add temporary storage to the result set otherwise: Select one of the unmarked elements in the collection and store it in the temporary collection Mark the element to be used Next level recursive function (End of this recursion) mark the element as unused Copy code

If you use the sequence 1 2 3 4 to represent such a backtracking process, you can use this picture to show:

There are many ideas to implement with code. It is necessary to need a List to store temporary results, but we also have two processing ideas for the original collection. The first is to use List to store the collection, and then remove it after use. Recurse the next layer and add to the original position after the recursion is complete. Another way of thinking is to use a fixed array for storage, and use a boolean array to mark the corresponding position after the used position, and then restore it after the recursion. Because List frequently finds, inserts and deletes, the efficiency is generally low, so we generally use a boolean array to mark whether the element at that position is used .

The specific implementation code is:

List<List<Integer>> list; public List<List<Integer>> permuteUnique( int [] nums) { list = new ArrayList<List<Integer>>(); //The final result List<Integer> team = new ArrayList<Integer>(); //Collect elements in the backtracking process boolean jud[] = new boolean [nums.length] ; //Used to mark dfs(jud, nums, team, 0 ); return list; } private void dfs ( boolean [] jud, int [] nums, List<Integer> team, int index) { int len = nums.length; if (index == len)//stop { list.add( new ArrayList<Integer>(team)); } else for ( int i = 0 ; i <len; i++) { if (jud[i]) //The current number has been used and is currently unavailable continue ; team.add(nums[i]); jud[i] = true ; //Mark the element to be used dfs(jud, nums, team, index + 1 ); jud[i] = false ; //restore team.remove(index); //remove the result from the temporary collection } } Copy code

Modify the output result to be consistent with the above mind map:

Neighborhood interchange method to achieve full arrangement without repetition

The backtracking test is tentative filling, which considers and assigns each position individually. Although the neighborhood exchange method is also implemented recursively, it is a strategy and idea based on exchange. It is also very simple to understand. The idea of neighborhood exchange is to consider from left to right.

Because the sequence is not repeated, we start to divide the array into two parts: the tentatively determined part and the undetermined part . At the beginning, it was the undetermined part. What we need to handle properly is the undetermined part. In the sequence of the undetermined part, we need to let every undetermined one have a chance to be in the undetermined first position, so the first element of the undetermined part must be exchanged with each one in turn (including themselves) After the exchange is completed, go down to recursively solve other possibilities, and after the solution is completed, exchange back (restore) and exchange with the following ones. In this way, when the recursion reaches the last level, the value of the array is added to the result set. If you don t understand, you can refer to the following figure to understand:

The implementation code is:

class Solution { public List<List<Integer>> permute( int [] nums) { List<List<Integer>>list = new ArrayList<List<Integer>>(); arrange(nums, 0 ,nums.length- 1 ,list); return list; } private void arrange ( int [] nums, int start, int end, List<List<Integer>> list) { if (start==end)//Add to the last one to the result { List<Integer>list2 = new ArrayList<Integer>(); for ( int a:nums) { list2.add(a); } list.add(list2); } for ( int i=start;i<=end;i++) //The undetermined part starts to exchange { swap(nums,i,start); arrange(nums, start+ 1 , end, list); swap(nums, i, start); //restore } } private void swap ( int [] nums, int i, int j) { int team=nums[i]; nums[i]=nums[j]; nums[j]=team; } } Copy code

So what s the difference between the neighborhood swap and the total permutation of the backtracking solution? 1. if the total permutation obtained by the backtracking method is ordered, the result is lexicographically ordered, because the strategy is to fill, first small and then large, and Neighborhood interchange does not have this feature. Secondly, the efficiency of neighborhood swap in this case is higher than that of the backtracking algorithm. Although the magnitude is similar, the backtracking algorithm needs to maintain a set of frequent additions and deletions, etc., occupying a certain amount of resources.

Full permutation with repetitive sequence

There are duplicates corresponding to the 47th question of Likou , which is described as:

Given a sequence that can contain repeated numbers

nums
, In any order, return all non-repeated permutations.

Example 1:

Input: nums = [1,1,2] Output: [[1,1,2], [1,2,1], [2,1,1]] Copy code

Example 2:

Input: nums = [1,2,3] Output: [[1,2,3],[1,3,2],[2,1,3],[2,3,1],[3,1,2],[3,2,1] ] Copy code

prompt:

1 <= nums.length <= 8 -10 <= nums[i] <= 10

This is slightly different from the non-repeated full array above. This input array may contain repeated sequences. How we adopt appropriate strategies to repeat is crucial. We also analyze the two methods of backtracking and neighborhood interchange.

The backtracking pruning method is slower than direct recursion because backtracking is complete, so the backtracking algorithm was not considered at the beginning, but the backtracking pruning method is better than the recursive neighborhood swap method. For the method that does not use hash deduplication, There is no suspense for sorting preprocessing first, and the key to the backtracking method is to avoid duplication of the same numbers due to relative order issues, so the relative positions of the same numbers must be unchanged in use , and the specific pruning rules are as follows :

  • Sort the sequence first
  • Place the data tentatively at the current location
    • If the current position number has been used, it cannot be used
    • If the current number is equal to the previous one but the previous one is not used, then the current number cannot be used and the previous number needs to be used.

The idea is very simple, and the realization is also very simple:

List<List<Integer>> list; public List<List<Integer>> permuteUnique( int [] nums) { list = new ArrayList<List<Integer>>(); List<Integer> team = new ArrayList<Integer>(); boolean jud[]= new boolean [nums.length]; Arrays.sort(nums); dfs(jud, nums, team, 0 ); return list; } private void dfs ( boolean [] jud, int [] nums, List<Integer> team, int index) { //TODO Auto-generated method stub int len = nums.length; if (index == len)//stop { list.add( new ArrayList<Integer>(team)); } else for ( int i = 0 ; i <len; i++) { if (jud[i]||(i> 0 &&nums[i]==nums[i- 1 ]&&!jud[i- 1 ])) //The current number has been used or the previous one is not used yet, it is currently unavailable continue ; team.add(nums[i]); jud[i]= true ; dfs(jud, nums, team, index + 1 ); jud[i] = false ; //restore team.remove(index); } } Copy code

Neighborhood Exchange

When we perform recursive full permutation, the main consideration is to get rid of the repetitive situation. How to remove the repetition of neighborhood exchange?

The method of using HashSet will not be discussed here. When we exchange the swap, it will be from front to back. After the previous is confirmed, it will not move, so we must carefully consider whom to exchange with . For example, the first number of 1 1 2 3 has three cases instead of four cases (two 1 1 2 3 is a result) :

1 1 2 3//0 0 position exchange 2 1 1 3//0 2 position exchange 3 1 2 1//0 3 position exchange

In addition, for example, the 3 1 1 sequence, 3 exchanges with myself, and the next two 1s can only be exchanged with one of them. Here we can agree to exchange with the first one. Let s look at a diagrammatic part of the process:

Therefore, when we start with an index, we must remember the following rule: the same number is exchanged only once (including the number whose value is equal to itself). When judging whether the latter value appears, you can traverse or use hashSet(). Of course, the pain point of this method is that the efficiency of judging the latter number is low. So in the case of possible duplication, this method is generally efficient.

The specific implementation code is:

public List<List<Integer>> permuteUnique( int [] nums) { List<List<Integer>> list = new ArrayList<List<Integer>>(); arrange(nums, 0 , nums.length- 1 , list); return list; } private void arrange ( int [] nums, int start, int end, List<List<Integer>> list) { if (start==end) { List<Integer>list2 = new ArrayList<Integer>(); for ( int a:nums) { list2.add(a); } list.add(list2); } Set<Integer>set = new HashSet<Integer>(); for ( int i=start;i<=end;i++) { if (set.contains(nums[i])) continue ; set.add(nums[i]); swap(nums,i,start); arrange(nums, start + 1 , end, list); swap(nums, i, start); } } private void swap ( int [] nums, int i, int j) { int team=nums[i]; nums[i]=nums[j]; nums[j]=team; } Copy code

Combination problem

Combination problems can be considered as a variant of full permutation. Problem description ( 77 questions ):

Given two integers n and k, return all possible combinations of k numbers in 1...n.

Example:

Input: n = 4, k = 2 Output: [ [2,4], [3,4], [2,3], [1,2], [1,3], [1,4], ] Copy code

analysis:

This problem is a classic retrospective problem. The combination needs to remember to only look at the elements and not the order of the elements, such as

ab
with
ba
It's the same combination. To avoid such repetition is the core , and to avoid such repetition, you need to save the position of the currently selected element with an int type. Next time, you can only traverse the numbers behind the selected subscript position, and the number of k can be achieved by a number type. Record the number of processed numbers back to the current layer to control.

The specific implementation is also very easy. It is necessary to create an array to store the corresponding number, and use the boolean array to determine whether the corresponding position number is used. Here, there is no need to store the number in the List. Finally, it is feasible to add the value to the result by judging the boolean array. The implementation code is:

class Solution { public List<List<Integer>> combine( int n, int k) { List<List<Integer>> valueList = new ArrayList<List<Integer>>(); //Result int num[] = new int [n]; //Array storage 1-n boolean jud[] = new boolean [n ]; //Used to determine whether to use for ( int i = 0 ;i<n;i++) { num[i]=i+ 1 ; } List<Integer>team = new ArrayList<Integer>(); dfs(num,- 1 ,k,valueList,jud,n); return valueList; } private void dfs ( int [] num, int index, int count,List<List<Integer>> valueList, boolean jud[], int n) { if (count== 0 )//k elements full { List<Integer>list = new ArrayList<Integer>(); for ( int i = 0 ;i<n;i++) { if (jud[i]) { list.add(i+ 1 ); } } valueList.add(list); } else { for ( int i=index+ 1 ;i<n;i++) //Can only traverse backtracking downward after index { jud[i]= true ; dfs(num, i, count- 1 , valueList,jud,n); jud[i]= false ; //restore } } } } Copy code

Subset

The subset problem is somewhat similar to the combination. Here are two cases of no repetition and repetition in the array.

Unrepeatable array subset

Problem description ( 78 questions ):

Give you an integer array nums, the elements in the array are different from each other. Return all possible subsets (power sets) of this array.

The solution set cannot contain duplicate subsets. You can return the solution set in any order.

Example 1:

Input: nums = [1,2,3] Output: [[],[1],[2],[1,2],[3],[1,3],[2,3],[1,2,3]] Copy code

Example 2:

Input: nums = [0] Output: [[],[0]] Copy code

prompt:

1 <= nums.length <= 10 -10 <= nums[i] <= 10 All elements in nums are different from each other

The subset is somewhat similar to the above combination. Of course, we don t need to judge how many, we just need to recurse to the end according to the strategy of combined backtracking . Each recursive function performed is a situation that must be added to the result (because The strategy will not be repeated).

The implemented code is:

class Solution { public List<List<Integer>> subsets( int [] nums) { List<List<Integer>> valueList = new ArrayList<List<Integer>>(); boolean jud[]= new boolean [nums.length]; List<Integer>team = new ArrayList<Integer>(); dfs(nums,- 1 ,valueList,jud); return valueList; } private void dfs ( int [] num, int index,List<List<Integer>> valueList, boolean jud[]) { { //Every recursive function must be added to the result List<Integer>list = new ArrayList<Integer>(); for ( int i = 0 ;i<num.length;i++) { if (jud[i]) { list.add(num[i]); } } valueList.add(list); } { for ( int i=index+ 1 ;i<num.length;i++) { jud[i]= true ; dfs(num, i, valueList,jud); jud[i]= false ; } } } } Copy code

There are duplicate array subsets

Topic description ( 90 questions with force deduction ):

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

Note: The solution set cannot contain duplicate subsets.

Example:

Input: [1,2,2] Output: [ [2], [1], [1,2,2], [2,2], [1,2], [] ] Copy code

The difference from the above non-repeated array subsetting is that there may be repeated elements . We need to filter out duplicate elements in the results.

First of all, the subset problem is undoubtedly the result of using the backtracking method. 1. if the sequence is not repeated, we will use a boolean[] array to mark the used elements and index to indicate the current subscript. When we backtrack, we Only recurse backwards and set the enumerated element boolean[index] to true (restore when you come back). Each recursive collection of true elements in the boolean[] array is one of the subsets. And dealing with duplicate elements, and processing is very similar to the previous full array, the first to be sorted , and then performing recursive processing when it came to the same element only allows the first continuous use from jumping is not allowed to use, so When recursively down, you need to determine whether the conditions are met (the first element is either different from the previous one or the same as the previous one and the previous one has been used ). For details, please refer to this picture:

The implementation code is:

class Solution { public List<List<Integer>> subsetsWithDup( int [] nums) { Arrays.sort(nums); boolean jud[]= new boolean [nums.length]; List<List<Integer>> valueList = new ArrayList<List<Integer>>(); dfs(nums,- 1 ,valueList,jud); return valueList; } private void dfs ( int [] nums, int index, List<List<Integer>> valueList, boolean [] jud) { //TODO Auto-generated method stub List<Integer>list = new ArrayList<Integer>(); for ( int i = 0 ;i<nums.length;i++) { if (jud[i]) { list.add(nums[i]); } } valueList.add(list); for ( int i=index+ 1 ;i<nums.length;i++) { //The first element or the current element is not the same as the previous one or the same and the previous one is used can continue if ((i== 0 )||(nums[i]!=nums[i- 1 ])|| (i> 0 &&jud[i- 1 ]&&nums[i]==nums[i- 1 ])) { jud[i]= true ; dfs(nums, i, valueList,jud); jud[i]= false ; } } } } Copy code

Concluding remarks

So far, the whole permutation, combination, and subset problems of this article are introduced here, and we must pay special attention to the ideas and strategies of problem handling and de-duplication. Of course, there are many problems similar to this, and you can master it with one more brush. Stay tuned later!

WeChat search: bigsai pay more attention to more exciting! Like the handsome guys and beauties, I wish you a happy study and get off the list as soon as possible!