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){
            res.add(new ArrayList<Integer>(temp));
            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;
            temp.add(num[i]);
            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){
            res.add(new ArrayList<Integer>(temp));
            return;
        }
        //Traverse all elements and select one to join
        for(int i = 0; i < num.length; i++){
            //If the element has already been added, there is no need to add it again
            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
            temp.add(num[i]);
            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;
        res.add(new ArrayList<>(list));
        //The next selection starts from the position selected last time
        for(int i=index;i<nums.length;i++){
            //Select the current number
            list.add(nums[i]);
            //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){
        res.add(new ArrayList<>(list));
        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;
            list.add(nums[i]);
            //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;
        if(sum==target) res.add(new ArrayList<>(list));
        for(int i=index;i<nums.length;i++){
            list.add(nums[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;
        if(sum==target) res.add(new ArrayList<>(list));
        for(int i=index;i<nums.length;i++){
            if(flag[i]||(i>0&&nums[i]==nums[i-1]&&!flag[i-1])) continue;
            list.add(nums[i]);
            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;
        if(sum==n&&cnt==k) res.add(new ArrayList<>(list));
        for(int i=index;i<nums.length;i++){
            list.add(nums[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;
        if(cnt==k) res.add(new ArrayList<>(list));
        for(int i=index;i<nums.length;i++){
            list.add(nums[i]);
            // A certain position cannot be selected multiple times, and the parameter in dfs is i+1 position
            dfs(i+1,nums,res,list,cnt+1,k);
            list.remove(list.size()-1);

        }
    }
}