代码随想录day21 | leetcode 77.组合 77.组合 加剪枝操作 216.组合总和III

组合

对于startIndex的变化，如何实现增大于减小。关键在于进栈，于连续出栈，重新入栈。

1. 第一次调用backtracking(3, 2, 1)

   • startIndex = 1
   • 进入for循环，i = 1
     • path.push_back(1) → path变为[1]
     • 递归调用backtracking(3, 2, 2)→进栈
       • 栈: [backtracking(3, 2, 2)]

2. 第二次调用backtracking(3, 2, 2)

   • startIndex = 2
   • 进入for循环，i = 2
     • path.push_back(2) → path变为[1, 2]
     • 递归调用backtracking(3, 2, 3)→进栈
       • 栈: [backtracking(3, 2, 2), backtracking(3, 2, 3)]

3. 第三次调用backtracking(3, 2, 3)

   • startIndex = 3

   • 进入for循环，i = 3

     • path.push_back(3) → path变为[1, 2, 3]

     • path.size() == k → 找到一个组合

     • result.push_back(path) → result变为[[1, 2, 3]]

     • 返回→出栈

       • 栈: [backtracking(3, 2, 2)]

       ！！！栈内有2个未出栈，实现了StartIndex – 操作。

class Solution {
     List<List<Integer>> result = new ArrayList<>();
    LinkedList<Integer> path = new LinkedList<>();
    public List<List<Integer>> combine(int n, int k) {
         backtracking(n,k,1);
        return result;
    }
      public void backtracking(int n,int k ,int startIndex){
        if (path.size() == k){
            result.add(new ArrayList<>(path));
            return;
        }

        for (int i = startIndex; i <= n; i++) {
            path.add(i);
            backtracking(n,k,i+1);
            path.removeLast();
        }
    }
}

组合优化

省去树的分支，剪枝的地方就在递归中每一层的for循环所选择的起始位置。

如果for循环选择的起始位置之后的元素个数 已经不足 我们需要的元素个数了，那么就没有必要搜索了。

优化过程如下：

已经选择的元素个数：path.size();

还需要的元素个数为: k - path.size();

在集合n中至多要从该起始位置 : n - (k - path.size()) + 1，开始遍历

为什么有个+1呢，因为包括起始位置，我们要是一个左闭的集合。

举个例子，n = 4，k = 3， 目前已经选取的元素为0（path.size为0），n - (k - 0) + 1 即 4 - ( 3 - 0) + 1 = 2。

class Solution {
     List<List<Integer>> result = new ArrayList<>();
    LinkedList<Integer> path = new LinkedList<>();
    public List<List<Integer>> combine(int n, int k) {
         backtracking(n,k,1);
        return result;
    }
      public void backtracking(int n,int k ,int startIndex){
        if (path.size() == k){
            result.add(new ArrayList<>(path));
            return;
        }

        for (int i = startIndex; i <= n-(k-path.size())+1; i++) {//改动
            path.add(i);
            backtracking(n,k,i+1);
            path.removeLast();
        }
    }
}

组合总和III

题目：找出所有相加之和为 n 的 k 个数的组合，且满足下列条件：

只使用数字1到9
每个数字 最多使用一次
返回 所有可能的有效组合的列表 。该列表不能包含相同的组合两次，组合可以以任何顺序返回。

class Solution {
   
     List<List<Integer>> result = new ArrayList<>();
    LinkedList<Integer> path = new LinkedList<>();

    public List<List<Integer>> combinationSum3(int k, int n) {
          backtracking(n,k,0,1);
        return result;
    }

    public void backtracking(int n,int k ,int sum ,int startIndex){
        
        if (sum > n) {
			return;
		}

        if (path.size() == k){
            if(n == sum){
            result.add(new ArrayList<>(path));
            
            }
           
           return;
        }

        for (int i = startIndex; i <= 9 && sum + i <= n; i++) {

            path.add(i);
            sum += i;
            backtracking(n,k,sum,i+1);
           
            path.removeLast();
            sum -= i;
        }
    }
}