# [Recursive backtracking full series-full permutation problem-subset problem-combination problem]

## one. Full arrangement - no repeated elements

### 1.1 Description of the topic

Given an array nums with no duplicate numbers, return all possible full permutations of it. You can return answers in any order.

Example 1:

Input: nums = [1,2,3 ]
Output: [[1,2,3],[1,3,2],[2,1,3],[2,3,1],[3,1,2],[3,2,1] ]
Example 2:

Input: nums = [0,1]
Output: [[0,1],[1,0]]
Example 3:

input: nums = [1]
output: [[1]]

hint:

1 <= nums.length <= 6
-10 <= nums[i] <= 10
All integers in nums are distinct from each other

### 1.2 Solution idea & implementation code

```class Solution {
public List<List<Integer>> permute(int[] nums) {
int n=nums.length;
List<List<Integer>> res = new ArrayList<>();
List<Integer> temp = new ArrayList<Integer>();
boolean[] flag=new boolean[n];
recursion(res, nums, temp,flag);
return res;
}
public void recursion(List<List<Integer>> res, int[] num, List<Integer> temp,boolean[] flag){
//When the temporary array is full, join the output
if(temp.size() == num.length){
return;
}
//Traverse all elements and select one to join
for(int i = 0; i < num.length; i++){
if(flag[i]) continue;
if(i > 0 && num[i - 1] == num[i]&&!flag[i-1])
//The current element num[i] is the same as the previous element num[i-1] of the same layer and num[i-1] has been used
continue;
//join array
flag[i]=true;
recursion(res, num, temp,flag);
flag[i]=false;
temp.remove(temp.size() - 1);
}
}

}
```

## two. Full alignment - with repeating elements

### 2.1 Description of the topic

Given a sequence nums that may contain repeating numbers, return all non-repeating full permutations in any order.

Example 1:

Input: nums = [1,1,2]
output:
[[1,1,2],
[1,2,1],
[2,1,1]]
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] ]

hint:

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

### 2.2 Solution idea & implementation code

```class Solution {
public List<List<Integer>> permuteUnique(int[] num) {
//Sort lexicographically first
Arrays.sort(num);
Boolean[] vis = new Boolean[num.length];
Arrays.fill(vis, false);
List<List<Integer>> res = new ArrayList<>();
List<Integer> temp = new ArrayList<Integer>();
recursion(res, num, temp, vis);
return res;
}

public void recursion(List<List<Integer>> res, int[] num, List<Integer> temp, Boolean[] vis){
//When the temporary array is full, join the output fast-template
if(temp.size() == num.length){
return;
}
//Traverse all elements and select one to join
for(int i = 0; i < num.length; i++){
if(vis[i])
continue;
if(i > 0 && num[i - 1] == num[i] && !vis[i - 1])
//The current element num[i] is the same as the previous element num[i-1] of the same layer and num[i-1] has been used
continue;
//marked as used
vis[i] =  true;
//join array
recursion(res, num, temp, vis);
//Backtrack
vis[i] =  false;
temp.remove(temp.size() - 1);
}
}

}
```

## three. Subset - no duplicate elements

### 3.1 Description of the topic

You are given an array nums of integers whose elements are distinct from each other. Returns all possible subsets (power sets) of this array.

A solution set cannot contain duplicate subsets. You can return solution sets in any order.

Example 1:

Input: nums = [1,2,3]
Output: [[],[1],[2],[1,2],[3],[1,3],[2,3],[1,2,3]]
Example 2:

input: nums = [0]
Output: [[],[0]]

hint:

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

### 3.2 Solution idea & implementation code

```class Solution {
public List<List<Integer>> subsets(int[] nums) {
int n=nums.length;
List<List<Integer>> res=new ArrayList<>();
List<Integer> list=new ArrayList<>();
if(n==0) return res;
dfs(0,nums,res,list);
return res;
}

public void dfs(int index,int[] nums,List<List<Integer>> res,List<Integer> list){
if(index>nums.length) return;
//The next selection starts from the position selected last time
for(int i=index;i<nums.length;i++){
//Select the current number
//continue recursive search
dfs(i+1,nums,res,list);
//remove the last number
list.remove(list.size()-1);
}
}
}
```

## Four. Subset - has repeated elements

### 4.1 Description of the topic

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

A solution set cannot contain duplicate subsets. In the returned solution set, the subsets can be in any order.

Example 1:

Input: nums = [1,2,2]
Output: [[],[1],[1,2],[1,2,2],[2],[2,2]]
Example 2:

input: nums = [0]
Output: [[],[0]]

hint:

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

### 4.2 Solution idea & implementation code

```class Solution {
public List<List<Integer>> subsetsWithDup(int[] nums) {
int n=nums.length;
List<List<Integer>> res=new ArrayList<>();
List<Integer> list=new ArrayList<>();
if(n==0) return res;
Arrays.sort(nums);
boolean[] flag=new boolean[n];
dfs(0,nums,res,list,flag);
return res;
}

public void dfs(int index,int[] nums,List<List<Integer>> res,List<Integer> list,boolean[] flag){
if(index>=nums.length) return;
//The next selection starts from the position selected last time
for(int i=index;i<nums.length;i++){
if(flag[i]||(i>0&&nums[i]==nums[i-1]&&!flag[i-1])) continue;
//Select the current number
flag[i]=true;
//continue recursive search
dfs(i+1,nums,res,list,flag);
//remove the last number
list.remove(list.size()-1);
flag[i]=false;
}
}
}
```

## Fives. Combination totals - no repeating elements + numbers can be repeated + there is a total limit

### 5.1 Description of the topic

Given an integer array candidates without repeated elements and a target integer target, find all the different combinations in candidates that can make the sum of the numbers target the target number, and return them in the form of a list. You can return these combinations in any order.

The same number in candidates can be selected repeatedly without limit. Two combinations are different if the chosen number of at least one number is different.

For a given input, the number of different combinations that sum to target is guaranteed to be less than 150.

Example 1:

Input: candidates = [2,3,6,7], target = 7
Output: [[2,2,3],[7]]
Explanation:
2 and 3 can form a set of candidates, 2 + 2 + 3 = 7. Note 2 can be used multiple times.
7 is also a candidate, 7 = 7 .
There are only these two combinations.
Example 2:

Input: candidates = [2,3,5], target = 8
Output: [[2,2,2,2],[2,3,3],[3,5]]
Example 3:

Input: candidates = [2], target = 1
output: []

hint:

1 <= candidates.length <= 30
2 <= candidates[i] <= 40
All elements of candidates are different from each other
1 <= target <= 40

### 5.2 Solution idea & implementation code

```class Solution {
public List<List<Integer>> combinationSum(int[] candidates, int target) {
int n=candidates.length;
List<List<Integer>> res=new ArrayList<>();
List<Integer> list=new ArrayList<>();
if(n==0) return res;
Arrays.sort(candidates);
dfs(0,candidates,res,list,0,target);
return res;
}

public void dfs(int index,int[] nums,List<List<Integer>> res,List<Integer> list,int sum,int target){
//End condition judgment
if(sum>target) return;
for(int i=index;i<nums.length;i++){
// A certain position can be selected multiple times, and the parameter is still i position in dfs
dfs(i,nums,res,list,sum+nums[i],target);
list.remove(list.size()-1);
}
}
}
```

## 6.Total number of combinations - there are repeated elements + numbers cannot be repeated + there is a total limit

### 6.1 Description of the topic

Given a set of candidate numbers candidates and a target number target, find all combinations in candidates that can make the sum of numbers into target.

Each number in candidates can only be used once in each combination.

Note: A solution set cannot contain duplicate combinations.

Example 1:

Input: candidates = [10,1,2,7,6,1,5], target = 8,
output:
[
[1,1,6],
[1,2,5],
[1,7],
[2,6]
]
Example 2:

Input: candidates = [2,5,2,1,2], target = 5,
output:
[
[1,2,2],
[5]
]

hint:

1 <= candidates.length <= 100
1 <= candidates[i] <= 50
1 <= target <= 30

### 6.2 Solution idea & implementation code

```class Solution {
public List<List<Integer>> combinationSum2(int[] candidates, int target) {
int n=candidates.length;
List<List<Integer>> res=new ArrayList<>();
List<Integer> list=new ArrayList<>();
if(n==0) return res;
Arrays.sort(candidates);
boolean[] flag=new boolean[n];
dfs(0,candidates,res,list,0,target,flag);
return res;
}

public void dfs(int index,int[] nums,List<List<Integer>> res,List<Integer> list,int sum,int target,boolean[] flag){
//End condition judgment
if(sum>target) return;
for(int i=index;i<nums.length;i++){
if(flag[i]||(i>0&&nums[i]==nums[i-1]&&!flag[i-1])) continue;
flag[i]=true;
// A certain position cannot be selected multiple times, and the parameters start from the next position when dfs
dfs(i+1,nums,res,list,sum+nums[i],target,flag);
list.remove(list.size()-1);
flag[i]=false;
}
}
}
```

## seven. Total number of combinations - no repeating elements + numbers cannot be repeated + there is a limit on the number and sum

### 7.1 Description of the topic

Find all combinations of k numbers that add up to n and satisfy the following conditions:

Only use numbers 1 to 9
Use each number at most once
Returns a list of all possible valid combinations. The list cannot 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
No other combinations match.
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
No other combinations match.
Example 3:

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

hint:

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

### 7.2 Solution idea & implementation code

```class Solution {
public List<List<Integer>> combinationSum3(int k, int n) {
int[] nums=new int[9];
for(int i=1;i<=9;i++){
nums[i-1]=i;
}
List<List<Integer>> res=new ArrayList<>();
List<Integer> list=new ArrayList<>();
if(n==0) return res;
dfs(0,nums,res,list,0,k,0,n);
return res;
}

public void dfs(int index,int[] nums,List<List<Integer>> res,List<Integer> list,int cnt,int k,int sum,int n){
//End condition judgment
if(sum>n||cnt>k) return;
for(int i=index;i<nums.length;i++){
// A certain position can be selected multiple times, and the parameter is still i position in dfs
dfs(i+1,nums,res,list,cnt+1,k,sum+nums[i],n);
list.remove(list.size()-1);

}
}
}
```

## Eight. Combination - no repeating elements + numbers cannot be selected multiple times + there is a limit on the number

### 8.1 Description of the topic

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

You can return answers in any order.

Example 1:

Input: n = 4, k = 2
output:
[
[2,4],
[3,4],
[2,3],
[1,2],
[1,3],
[1,4],
]
Example 2:

Input: n = 1, k = 1
output: [[1]]

hint:

1 <= n <= 20
1 <= k <= n

### 8.2 Solution idea & implementation code

```class Solution {
public List<List<Integer>> combine(int n, int k) {
int[] nums=new int[n];
for(int i=1;i<=n;i++){
nums[i-1]=i;
}
List<List<Integer>> res=new ArrayList<>();
List<Integer> list=new ArrayList<>();
if(n==0) return res;
dfs(0,nums,res,list,0,k);
return res;
}

public void dfs(int index,int[] nums,List<List<Integer>> res,List<Integer> list,int cnt,int k){
//End condition judgment
if(cnt>k) return;