LeetCode 回溯算法刷新日记 (I) - 组合

LeetCode题目链接

给定一个整数n和一个整数k，要求返回[1, n]中所有可能的k个数的组合

首先的话需要知道组合的特点是顺序不重要，这启示我们可以用列表来存????????????

我们来梳理逻辑

• 回溯法的核心是用递归来构建每一个可能的组合，通过递归遍历所有可能的数并在选择时跳过已经选择过的数字????，所以我们可以定义一个结果列表result，一个组合列表path，一个数字索引startIndex，每层往下数字索引递增，选择数字加入path，当path的长度等于k则把组合加入结果集，递归完成后回溯path来存储其他组合????

我们来进一步梳理回溯三要素

• 递归函数的参数和返回值

//把结果集和组合定义为全局变量，避免太多参数导致递归处理不好理解
List<List<Integer>> result = new ArrayList<>();//存放符合条件结果的集合 List<Integer> path = new ArrayList<>();//存放符合条件的结果

//递归处理无返回值，递归完result已经填充完毕，n为数的最大值，k为组合大小，在递归处理中需要
private void backtracking(int n, int k, int startIndex){}

• 回溯函数终止条件（这里要生成path副本来存入结果集中，如果存path的话只是一个引用，path回溯撤销时，result中的元素也将同时撤销????????????）

if(path.size() == k){ //终止条件:组合长度等于k
    result.add(new ArrayList<>(path));//存放结果
    return;
}

• 单层搜索过程(这里是包含未剪枝处理的搜索逻辑与剪枝的搜索逻辑，因为有些不必要的搜索可以剪掉????????????，剪掉这些搜索就称为剪枝，这里剪枝是因为要组合长度为k，然后如果数字索引到后面总的搜索次数都不够添加k个元素形成一个组合那就没有必要搜索了????????????)

for(int i = startIndex; i <= n; i++){//选择本层集合中的元素
    path.add(i);//处理节点
    backtracking(n, k, i + 1);//递归
    path.removeLast();//回溯撤销处理的节点
}
for(int i = startIndex; i <= n - (k - path.size()) + 1; i++){//选择本层集合中的元素
    path.add(i);//处理节点
    backtracking(n, k, i + 1);//递归
    path.removeLast();//回溯撤销处理的节点
}

回溯的完整代码如下

//未剪枝
// class Solution {
//     List<List<Integer>> result = new ArrayList<>();//存放符合条件结果的集合
//     List<Integer> path = new ArrayList<>();//存放符合条件的结果
//     public List<List<Integer>> combine(int n, int k) {
//         backtracking(n, k, 1);
//         return result;
//     }

//     private 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();//回溯撤销处理的节点
        // }
//     }
// }

//剪枝
class Solution {
    List<List<Integer>> result = new ArrayList<>();//存放符合条件结果的集合
    List<Integer> path = new ArrayList<>();//存放符合条件的结果
    public List<List<Integer>> combine(int n, int k) {
        backtracking(n, k, 1);
        return result;
    }

    private void backtracking(int n, int k, int startIndex){ //可剪枝处
        if(path.size() == k){ //终止条件
            result.add(new ArrayList<>(path));//存放结果
            return;
        }
        /**
        如果for循环选择的起始位置之后的元素个数已经不足我们需要的元素个数那就没有必要搜索了
        已经选择的元素path.size()
        还需要选择的元素k - path.size()
        在集合中至多要从n - (k - path.size()) + 1开始遍历
         */
        for(int i = startIndex; i <= n - (k - path.size()) + 1; i++){//选择本层集合中的元素
            path.add(i);//处理节点
            backtracking(n, k, i + 1);//递归
            path.removeLast();//回溯撤销处理的节点
        }
    }
}

---