1. 题目描述（中等难度）

[warning] 77. 组合

2. 解法一：回溯

回溯算法模板

class Solution {
    void backtracking(参数) {
        if (终⽌条件){
            存放结果;
            return;
        }
        for (选择：本层集合中元素（树中节点孩⼦的数量就是集合的⼤⼩）){
            处理节点;
            backtracking(路径，选择列表); // 递归
            回溯，撤销处理结果
        }
    }
}

class Solution {
    List<List<Integer>> resp = new ArrayList<>();
    Deque<Integer> ans = new LinkedList<>();
    public List<List<Integer>> combine(int n, int k) {
        if (k <= 0 || n < k) {
            return resp;
        }
        backTracking(n,k,1);
        return resp;
    }

    public void backTracking(int n,int k,int startIndex){
        if(ans.size() == k){
          resp.add(new LinkedList<>(ans));  
          return;
        }
        for(int i=startIndex;i<=n;i++){
            ans.offerLast(i);
            backTracking(n,k,i+1);
            ans.pollLast();
        }
    }
}

class Solution {
    List<List<Integer>> resp = new ArrayList<>();
    List<Integer> ans = new ArrayList<>();
    public List<List<Integer>> combine(int n, int k) {
        if (k <= 0 || n < k) {
            return resp;
        }
        backTracking(n,k,1);
        return resp;
    }

    public void backTracking(int n,int k,int startIndex){
        if(ans.size() == k){
          resp.add(new ArrayList<>(ans));  
          return;
        }
        for(int i=startIndex;i<=n;i++){
            ans.add(i);
            backTracking(n,k,i+1);
            ans.remove(ans.size()-1);
        }
    }
}

剪支 搜索起点的上界 + 接下来要选择的元素个数 - 1 = n 搜索起点的上界 = n - (k - path.size()) + 1

class Solution {
    List<List<Integer>> resp = new ArrayList<>();
    List<Integer> ans = new ArrayList<>();
    public List<List<Integer>> combine(int n, int k) {
      if(n<=0 || k>n){
          return resp;
      }
      backTracking(n,k,1);
      return resp;

    }
    public void backTracking(int n,int k,int startIndex){
      if(ans.size() == k){
          resp.add(new ArrayList<>(ans));
          return;
      }

      for(int i=startIndex;i<=n-(k-ans.size())+1;i++){
          ans.add(i);
          backTracking(n,k,i+1);
          ans.remove(ans.size()-1);
      }
    }
}