回溯法

回溯法主要解决的问题类型：
组合问题：N个数里面按一定规则找出k个数的集合
切割问题：一个字符串按一定规则有几种切割方式
子集问题：一个N个数的集合里有多少符合条件的子集
排列问题：N个数按一定规则全排列，有几种排列方式
棋盘问题：N皇后，解数独等等

77. 组合

题目

class Solution {
    List<List<Integer>> ans = new ArrayList<>();
    public List<List<Integer>> combine(int n, int k) {
        backtracking(1,n,k,new ArrayList<>());
        return ans;
    }
    void backtracking(int minNum, int maxNum, int count, List<Integer> in){
        if (count == 0){
            ans.add(new ArrayList<>(in));
            return;
        }
        for (int i = minNum; i <= maxNum; i++){
            in.add(i);
            backtracking(i+1,maxNum,count - 1,in);
            in.remove(in.size() - 1);
        }
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18