回溯算法基本思想及其实现

梦里梦外; 2023-10-12 16:20 49阅读 0赞

#### 文章目录 ####

*  基本思想
 *  回溯算法的递归框架
 *   *  组合问题
     *  组合总和
     *  组合去重
     *  子集
     *  全排列

## 基本思想 ##

回溯算法是一种递归算法，它试图通过尝试不同的选择，解决一个问题。它的基本思想是从可能的决策开始搜索，如果发现这条路往下走不能得到有效的解答，就返回上一层重新选择另外一种可能的决策，并且重复以上的步骤。

具体来说，回溯算法通过深度优先搜索的方式，遍历问题的解空间。在深度优先搜索的过程中，当搜索到某一层时，根据问题的限制条件判断该层的节点状态是否满足条件。如果条件不满足，则这个节点的状态被排除，并回溯到当前节点的父节点，重新进行遍历。如果条件满足，则继续搜索下一层的节点，并重复以上操作，直到搜索到一个符合条件的解或者遍历完整个解空间。

回溯算法一般适用于求解组合问题、排列问题、搜索问题等。由于在搜索过程中，需要不断地重新选择和放弃某个状态，所以回溯算法具有空间复杂度为 O(N) 的特点。

因为回溯算法的搜索路径呈现树形结构，所以有时候也被称作"回溯搜索"或"深度优先搜索+状态撤销"算法。

## 回溯算法的递归框架 ##

回溯算法是一种典型的递归算法，它通常需要使用递归函数来实现。回溯算法的递归框架一般为以下形式：

def backtrack(candidate, state):
        if state == target:                        # 满足条件，输出结果
            output(candidate)
            return
        # 选择
        for choice in choices:
            make_choice(choice)                    # 做选择
            backtrack(candidate, state + 1)        # 递归进入下一层状态
            undo_choice(choice)                    # 撤销选择

这个递归框架通常包括三个部分：选择、递归和撤销选择。具体来说，每次迭代中，算法选择一个可用的状态或者变量，进行尝试。然后进入下一层状态，继续进行递归。如果递归过程中发现当前状态不符合要求，则需要撤销前面的选择，回到上一层状态，重新开始搜索。

在回溯算法中，重点是如何定义选择和撤销操作。这些操作通常和具体问题相关，需要根据问题的特点进行定义。回溯算法的实现应该包括以下步骤：

1.  判断是否到达了目标状态。当搜索到符合要求的状态时，将其输出，并结束搜索。
2.  选择当前状态或变量。在当前状态的所有可选序列、可选子节点等中，选择一个未被搜索过的状态或变量。
3.  尝试选择新状态。在进入下一层状态之前，需要先尝试选择新状态，完成相应的操作，比如加入选择列表等。
4.  递归进入下一层状态。进入下一层状态并继续搜索。
5.  撤销选择。如果当前状态不符合要求，需要撤销前面所做的所有选择、完成的操作等，返回上一层状态，继续搜索其他可选序列或子节点。

### 组合问题 ###

> LeetCode第77题：[https://leetcode.cn/problems/combinations/][https_leetcode.cn_problems_combinations]  
> ![在这里插入图片描述][08124b0ab6ce4ec6bcd7a1b76e97a4d5.png]

首先定义两个全局变量用于存放结果集和当前候选集合：

// 存放所有满足条件的结果
    List<List<Integer>> ans = new ArrayList<List<Integer>>();
    // 当前得到的候选集
    List<Integer> temp = new ArrayList<Integer>();

1.  递归的终止条件：找到了一个子集大小为k的组合，即

if (temp.size() == k) {
        
        ans.add(new ArrayList<Integer>(temp));
        return;
    }

1.  选择

for(int i = cur; i<=n;i++){
        
        temp.add(i);	// 当前元素加入候选集合
        dfs(i+1,n,k);	// 递归进入下一层状态
        temp.remove(temp.size() - 1);	// 当前元素移除候选集合
    }

完整代码

class Solution {
        
        List<List<Integer>> ans = new ArrayList<List<Integer>>();
        List<Integer> temp = new ArrayList<Integer>();
    
        public List<List<Integer>> combine(int n, int k) {
        
            dfs(1, n, k);
            return ans;
        }
    
        public void dfs(int cur, int n, int k) {
        
        		// 剪枝：可选的元素不足K个
            if (temp.size() + (n - cur + 1) < k) {
        
                return;
            }
            if (temp.size() == k) {
        
                ans.add(new ArrayList<Integer>(temp));
                return;
            }
    
            for(int i = cur; i<=n;i++){
        
                temp.add(i);
                dfs(i+1,n,k);
                temp.remove(temp.size() - 1);
            }
        }
    }

### 组合总和 ###

> LeetCode 第39题：组合总和：[https://leetcode.cn/problems/combination-sum/][https_leetcode.cn_problems_combination-sum]  
> ![在这里插入图片描述][720a0519032148ffbb7d6cf038ed0ea5.png]

首先定义两个全局变量用于存放结果集和当前候选集合：

// 存放所有满足条件的结果
    List<List<Integer>> ans = new ArrayList<List<Integer>>();
    // 当前得到的候选集
    List<Integer> temp = new ArrayList<Integer>();

1.  递归的终止条件：当前候选集合总和大于target或找到总和为target的组合，即

if(sum > target){
        
        return;
    }
    if(sum == target){
        
        res.add(new ArrayList<Integer>(temp));
        return;
    }

1.  选择

for(int i=index;i<candidates.length;i++){
        
        temp.add(candidates[i]);	// 当前元素加入候选集合
        sum+=candidates[i];			// 当前候选集总和
        dfs(candidates, target, i);	// 递归进入下一层状态
        // 当前元素移除候选集合
        sum -= temp.get(temp.size()-1);
        temp.remove(temp.size()-1);
    }

完整代码

class Solution {
        
        List<List<Integer>> res = new ArrayList<List<Integer>>();
        List<Integer> temp = new ArrayList<Integer>();
        int sum = 0;
        public List<List<Integer>> combinationSum(int[] candidates, int target) {
        
            dfs(candidates, target, 0);
            return res;
        }
    
        public void dfs(int[] candidates, int target, int index){
        
            if(sum > target){
        
                return;
            }
            if(sum == target){
        
                res.add(new ArrayList<Integer>(temp));
                return;
            }
            for(int i=index;i<candidates.length;i++){
        
                temp.add(candidates[i]);
                sum+=candidates[i];
                dfs(candidates, target, i);
                sum -= temp.get(temp.size()-1);
                temp.remove(temp.size()-1);
            }
        }
    }

### 组合去重 ###

> LeetCode第40题： 组合总和 II：[https://leetcode.cn/problems/combination-sum-ii/][https_leetcode.cn_problems_combination-sum-ii]  
> ![在这里插入图片描述][f71e25adcf9d4e6c9cb82dcc8349de3f.png]

在上一题组合求和基础上，定义一个used数组记录元素是否是否过：

1.  递归的终止条件：当前候选集合总和大于target或找到总和为target的组合，即

if(sum > target){
        
        return;
    }
    if(sum == target){
        
        res.add(new ArrayList<Integer>(temp));
        return;
    }

1.  选择

for(int i=cur;i<candidates.length;i++){
        
    	//当前元素是否有效
        if(i>0&&candidates[i]==candidates[i-1]&&used[i-1]==false){
        
            continue;
        }
        temp.add(candidates[i]);	// 当前元素加入候选集合
        used[i] = true;		// 标记当前元素已使用
        sum += candidates[i];		// 当前候选集总和
        dfs(candidates,target,i+1,sum,used);		// 递归进入下一层状态
        // 当前元素移除候选集合
        sum -= temp.get(temp.size() - 1);
        temp.remove(temp.size() - 1);
        used[i] = false;
    }
    for(int i=index;i<candidates.length;i++){
        
        temp.add(candidates[i]);	// 当前元素加入候选集合
        sum+=candidates[i];			// 当前候选集总和
        dfs(candidates, target, i);	// 递归进入下一层状态
        // 当前元素移除候选集合
        sum -= temp.get(temp.size()-1);
        temp.remove(temp.size()-1);
    }

完整代码

class Solution {
        
        List<List<Integer>> res = new ArrayList<List<Integer>>();
        List<Integer> temp = new ArrayList<Integer>();
        public List<List<Integer>> combinationSum2(int[] candidates, int target) {
        
            Arrays.sort(candidates);
            boolean[] used = new boolean[candidates.length];
            dfs(candidates, target, 0, 0, used);
            return res;
        }
    
        public void dfs(int[] candidates, int target, int cur, int sum, boolean[] used){
        
            if(sum > target){
        
                return;
            }
            if(sum == target){
        
                res.add(new ArrayList<Integer>(temp));
                return;
            }
    
            for(int i=cur;i<candidates.length;i++){
        
                if(i>0&&candidates[i]==candidates[i-1]&&used[i-1]==false){
        
                    continue;
                }
                temp.add(candidates[i]);
                used[i] = true;
                sum += candidates[i];
                dfs(candidates,target,i+1,sum,used);
                sum -= temp.get(temp.size() - 1);
                temp.remove(temp.size() - 1);
                used[i] = false;
            }
        }
    }

### 子集 ###

> 1.  子集: [https://leetcode.cn/problems/subsets/][https_leetcode.cn_problems_subsets]  
>     ![在这里插入图片描述][96ccf1e472704b65aba002f167ba82b3.png]

class Solution {
        
        List<List<Integer>> res = new ArrayList<List<Integer>>();
    
        Deque<Integer> temp = new ArrayDeque<Integer>();
        public List<List<Integer>> subsets(int[] nums) {
        
    
            dfs(nums, 0);
    
            return res;
        }
    
        public void dfs(int[] nums, int index){
        
            res.add(new ArrayList<Integer>(temp));
    
            for(int i=index;i<nums.length;i++){
        
                temp.addLast(nums[i]);
                dfs(nums, i+1);
                temp.removeLast();
            }
        }
    }

### 全排列 ###

> 1.  全排列: [https://leetcode.cn/problems/permutations/][https_leetcode.cn_problems_permutations]  
>     ![在这里插入图片描述][41303931a363416e9c8d2a21635ec400.png]

class Solution {
        
        List<List<Integer>> res = new ArrayList<List<Integer>>();
        List<Integer> temp = new ArrayList<Integer>();
        public List<List<Integer>> permute(int[] nums) {
        
            boolean[] used = new boolean[nums.length];
            dfs(nums, used, 0);
            return res;
        }
    
        public void dfs(int[] nums, boolean[] used, int index){
        
            if(temp.size() == nums.length){
        
                res.add(new ArrayList<Integer>(temp));
                return;
            }
            for(int i=0;i<nums.length;i++){
        
                if(used[i]){
        
                    continue;
                }
                used[i] = true;
                temp.add(nums[i]);
                dfs(nums, used, i+1);
                used[i] = false;
                temp.remove(temp.size()-1);
            }
        }
    }

[https_leetcode.cn_problems_combinations]: https://leetcode.cn/problems/combinations/
[08124b0ab6ce4ec6bcd7a1b76e97a4d5.png]: https://img-blog.csdnimg.cn/08124b0ab6ce4ec6bcd7a1b76e97a4d5.png
[https_leetcode.cn_problems_combination-sum]: https://leetcode.cn/problems/combination-sum/
[720a0519032148ffbb7d6cf038ed0ea5.png]: https://img-blog.csdnimg.cn/720a0519032148ffbb7d6cf038ed0ea5.png
[https_leetcode.cn_problems_combination-sum-ii]: https://leetcode.cn/problems/combination-sum-ii/
[f71e25adcf9d4e6c9cb82dcc8349de3f.png]: https://img-blog.csdnimg.cn/f71e25adcf9d4e6c9cb82dcc8349de3f.png
[https_leetcode.cn_problems_subsets]: https://leetcode.cn/problems/subsets/
[96ccf1e472704b65aba002f167ba82b3.png]: https://img-blog.csdnimg.cn/96ccf1e472704b65aba002f167ba82b3.png
[https_leetcode.cn_problems_permutations]: https://leetcode.cn/problems/permutations/
[41303931a363416e9c8d2a21635ec400.png]: https://img-blog.csdnimg.cn/41303931a363416e9c8d2a21635ec400.png