组合类型

组合本质：选哪个？

# 77. 组合 (opens new window)

正序：第一层：1,2,3,4，第二层：234,34,4,null；

class Solution {
    List<List<Integer>> res = new ArrayList<>();
    List<Integer> path = new ArrayList<>();
    int n;
    int k;
    public List<List<Integer>> combine(int n, int k) {
        this.n = n;
        this.k = k;
        dfs(1);
        return res;
    }
    void dfs(int i){
        if(path.size()==k){
            res.add(new ArrayList<>(path));
            return ;
        }
        for(int j=i;j<=n;j++){
            path.add(j);
            dfs(j+1);
            path.remove(path.size()-1);
        }
    }
}

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23

倒序：每次更新剩余次数，若当前选的数字 > 剩余可选个数，进行递归；

class Solution {
    List<List<Integer>> res = new ArrayList<>();
    List<Integer> path = new ArrayList<>();
    public List<List<Integer>> combine(int n, int k) {
        dfs(n,k);
        return res;
    }
    void dfs(int i,int k){
        int d = k-path.size();//剩余可选的数字
        if(d==0){
            res.add(new ArrayList<>(path));
            return ;
        }
        //相当于方法一的for循环，变成压栈
        if(i>d){
            dfs(i-1,k);
        }
        path.add(i);
        dfs(i-1,k);
        path.remove(path.size()-1);
    }
}

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22

# 216. 组合总和 III (opens new window)

class Solution {
    List<List<Integer>> ret = new ArrayList<>();
    List<Integer> path = new ArrayList<>();
    int k,target;
    public List<List<Integer>> combinationSum3(int k, int target) {
        this.k=k;
        this.target=target;
        dfs(1,target);
        return ret;
    }
    void dfs(int i,int target){
        if(target==0 && path.size()==k){
            ret.add(new ArrayList<>(path));
            return ;
        }
        for(int j=i;j<=9;j++){
            path.add(j);
            dfs(j+1,target-j);
            path.remove(path.size()-1);
        }
    }
}

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22

# 39. 组合总和 (opens new window)

class Solution {
    List<List<Integer>> ret = new ArrayList<>();
    List<Integer> path = new ArrayList<>();
    int[] candidates;
    int target;
    public List<List<Integer>> combinationSum(int[] candidates, int target) {
        this.candidates = candidates;
        this.target = target;
        dfs(0,target);
        return ret;
    }
    void dfs(int i,int target){
        if(target<0) return ;
        if(i<candidates.length && target==0){
            ret.add(new ArrayList<>(path));
            return ;
        }
        for(int j=i;j<candidates.length;j++){
            path.add(candidates[j]);
            dfs(j,target-candidates[j]);
            path.remove(path.size()-1);
        }
    }
}

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24

# 40. 组合总和 II (opens new window)

class Solution {
    List<List<Integer>> ret = new ArrayList<>();
    List<Integer> path = new ArrayList<>();
    int[] candidates;
    int target;
    public List<List<Integer>> combinationSum2(int[] candidates, int target) {
        this.candidates = candidates;
        this.target = target;
        Arrays.sort(candidates);
        dfs(0,target);
        return ret;
    }
    void dfs(int i,int target){
        if(target==0){
            ret.add(new ArrayList<>(path));
            return ;
        }
        for(int j=i;j<candidates.length;j++){
            if(target-candidates[i]<0){
                break;
            }
            if(j>i && candidates[j]==candidates[j-1]){
                continue;
            }
            path.add(candidates[j]);
            dfs(j+1,target-candidates[j]);
            path.remove(path.size()-1);
        }
    }
}

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30

# 17. 电话号码的字母组合 (opens new window)

class Solution {
    List<String> ret = new ArrayList<>();
    String[] arr;
    String digits;
    public List<String> letterCombinations(String digits) {
        this.arr = new String[]{"","","abc","def","ghi","jkl","mno","pqrs","tuv","wxyz"};
        this.digits = digits;
        if(digits==null || digits.length()==0){
            return ret;
        }
        dfs(0,new StringBuilder());
        return ret;
    }
    void dfs(int i,StringBuilder cur){
        if(i==digits.length()){
            ret.add(cur.toString());
            return ;
        }
        String str = arr[digits.charAt(i)-'0'];
        for(int j=0;j<str.length();j++){
            cur.append(str.charAt(j));
            dfs(i+1,cur);
            cur.deleteCharAt(cur.length()-1);
        }
    }
}

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26

# 22. 括号生成 (opens new window)

class Solution {
    List<String> ret = new ArrayList<>();
    public List<String> generateParenthesis(int n) {
        dfs(new StringBuilder(),n,n);
        return ret;
    }
    void dfs(StringBuilder cur,int l,int r){
        if(l==0 && r==0){
            ret.add(cur.toString());
            return ;
        }
        if(l<0 || r<0)
            return ;
        if(l>r)
            return ;
        cur.append('(');
        dfs(cur,l-1,r);
        cur.deleteCharAt(cur.length()-1);
        cur.append(')');
        dfs(cur,l,r-1);
        cur.deleteCharAt(cur.length()-1);
    }
}

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23

# 131. 分割回文串 (opens new window)

class Solution {
    List<List<String>> ret = new ArrayList<>();
    List<String> path = new ArrayList<>();
    String s;
    public List<List<String>> partition(String s) {
        this.s = s;
        dfs(0);
        return ret;
    }
    void dfs(int i){
        if(i==s.length()){
            ret.add(new ArrayList<>(path));
            return ;
        }
        for(int j=i;j<s.length();j++){
            if(f(s,i,j)){
                String str = s.substring(i,j+1);
                path.add(str);
            }else{
                continue;
            }
            dfs(j+1);
            path.remove(path.size()-1);
        }
    }
    boolean f(String s,int l,int r){
        for(int i=l,j=r;i<=j;i++,j--){
            if(s.charAt(i)!=s.charAt(j)){
                return false;
            }
        }
        return true;
    }
}

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34

# 93. 复原 IP 地址 (opens new window)

# 数字分解

题目描述：将正整数 n 分解为 m 个正整数之和，且后面的数必须大于前面的数；

案例：

输入：

7

3

输出：

[1, 2, 4]

public class Main {
    static int m;
    static List<List<Integer>> res = new ArrayList<>();
    static List<Integer> path = new ArrayList<>();
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt();
        m = sc.nextInt();
        dfs(n,0,0);
        for(List<Integer> item:res){
            System.out.println(Arrays.toString(item.toArray()));
            System.out.println();
        }
    }
    static void dfs(int sum,int cnt,int pre){
        if(sum==0 && cnt==m){
            res.add(new ArrayList<>(path));
            return ;
        }
        for(int j=pre+1;j<=sum;j++){
            path.add(j);
            dfs(sum-j,cnt+1,j);
            path.remove(path.size()-1);
        }
    }
}

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26

# 386. 字典序排数 (opens new window)

class Solution {
    List<Integer> ret = new ArrayList<>();
    public List<Integer> lexicalOrder(int n) {
        for(int i=1;i<10;i++)
            dfs(i,n);
        return ret;
    }
    void dfs(int cur,int limit){
        if(cur>limit)
            return ;
        ret.add(cur);
        for(int i=0;i<10;i++)
            dfs(cur*10+i,limit);
    }
}

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15

# 332. 重新安排行程 (opens new window)

# 2517. 礼盒的最大甜蜜度 (opens new window)

← 树上倍增子集类型→