回溯

回溯法思路的简单描述是：把问题的解空间转化成了图或者树的结构表示，然后使用深度优先搜索策略进行遍历，遍历的过程中记录和寻找所有可行解或者最优解。

回溯法的基本行为是搜索，搜索过程使用剪枝函数来为了避免无效的搜索。剪枝函数包括两类：1. 使用约束函数，剪去不满足约束条件的路径；2.使用限界函数，剪去不能得到最优解的路径。

回溯法实现————递归和迭代

/*
输入：candidates = [2,3,5], target = 8,
所求解集为：
[
  [2,2,2,2],
  [2,3,3],
  [3,5]
]
*/
class Solution {
    public List<List<Integer>> combinationSum(int[] candidates, int target) {
        List<List<Integer>> list = new ArrayList<List<Integer>>();
        List<Integer> node = new ArrayList<Integer>();
        dfs(candidates,target,0,node,list);
        return list;
    }
    public void dfs(int[] candidates,int target,int i,List<Integer>node,List<List<Integer>>list)
    {
        int length=candidates.length;
        if(i==length)return;
        if(target==0)
        {
            list.add(new ArrayList<Integer>(node));
            return;
        }
        dfs(candidates,target,i+1,node,list);
        if(target-candidates[i]>=0)
        {
            node.add(candidates[i]);
            target-=candidates[i];
            dfs(candidates,target,i,node,list);
            node.remove(node.size()-1);
        }
    }
}

leetcode 46.全排列

/*
输入: [1,2,3]
输出:
[
  [1,2,3],
  [1,3,2],
  [2,1,3],
  [2,3,1],
  [3,1,2],
  [3,2,1]
]
*/
class Solution {
    List<List<Integer>> list = new ArrayList<>();
    public List<List<Integer>> permute(int[] nums) {
        List<Integer> node = new ArrayList<Integer>();
        boolean[] visited = new boolean[nums.length];//判断该数有没有被选择
        dfs(node,nums,visited);
        return list;
    }
    public void dfs(List<Integer> node,int[]nums,boolean[]visited)
    {
        if(node.size()==nums.length)//递归结束条件
        {
            list.add(new ArrayList<>(node));
            return;
        }
        for(int i = 0;i<nums.length;i++)//在递归中使用for循环可以依次取nums中的每个元素当头。然后进入递归后可以构造出经过所有每一元素路径的遍历树
        {
            if(!visited[i])
            {
                node.add(nums[i]);
                visited[i]=true;
                dfs(node,nums,visited);
// 注意：下面这两行代码发生 「回溯」，回溯发生在从 深层结点 回到 浅层结点 的过程，代码在形式上和递归之前是对称的
                visited[i]=false;
                node.remove(node.size()-1);
            }
        }
        
    }
}

leetcode 47.全排列2

//全排列的两道题目和组合总和的两道题目本质上是差不多的，在存在重复数字的时候，这里采用的的方法是：
//将数组中的元素进行排列，然后针对重复的部分进行剪枝：遍历数组中每个元素当头时，当前后两个元素相同的时候跳过
class Solution {
    List<List<Integer>> list = new ArrayList<>();
    public List<List<Integer>> permuteUnique(int[] nums) {
        List<Integer> node = new ArrayList<Integer>();
        boolean visited[] = new boolean[nums.length];
        Arrays.sort(nums);
        dfs(node,nums,visited);
        
        return list;
    }
    public void dfs(List node,int[]nums,boolean[]visited)
    {
        if(node.size()==nums.length)
        {
            list.add(new ArrayList<>(node));
            return;
        }
        for(int i =0;i<nums.length;i++)
        {
            if(!visited[i])
            {
                //此处剪枝
                //i>0&&nums[i]==nums[i-1]的含义是当前后两个元素相同时，跳过后一个元素当头。
                //!visited[i-1]针对的是后续排列的时候当前面元素已被选择，跳过后面和他相同的元素
                if(i>0&&nums[i]==nums[i-1]&&!visited[i-1])continue;
                node.add(nums[i]);visited[i]=true;
                dfs(node,nums,visited);
                visited[i]=false;
                node.remove(node.size()-1);
            }
        }
    }
}

leetcode 77.组合

class Solution {
    List<List<Integer>> list = new ArrayList<>();
    public List<List<Integer>> combine(int n, int k) {
        List<Integer> node = new ArrayList<>();

        dfs(node,n,k,1);
        return list;
    }
    public void dfs(List node,int n,int k,int start)
    {
        if(node.size()==k)
        {
            list.add(new ArrayList<>(node));
            return;
        }
        for(int i=start;i<=n;i++,start++)
            //start++表示的意思是递减剩下待取的元素
           //算法优化：i<=n-k+node.size()+1
            //优化将循环的次数减少到待取元素的大小
        {
                node.add(i);
                dfs(node,n,k,start+1);
                node.remove(node.size()-1);
        }

    }
}

leetcode 78.子集

class Solution {
    List<List<Integer>> list = new ArrayList<>();
    public List<List<Integer>> subsets(int[] nums) {
        List<Integer>node = new ArrayList<>();
        if(nums.length==0)return list;
        for(int i=0;i<=nums.length;i++)
        dfs(node,nums,i,0);
        return list;
    }
    public void dfs(List<Integer> node,int[]nums,int number,int start)
    {
        if(node.size()==number)
        {
            list.add(new ArrayList<>(node));return;
        }
        for(int i =start;i<nums.length;i++)
        {
            node.add(nums[i]);
                    //这里的i+1避免了元素重复
            dfs(node,nums,number,i+1);
            node.remove(node.size()-1);
        }
    }
}

leetcode 90.子集2

想在子集1的基础上进行修改，但是去重实现的不好，暂时不知道怎么处理

/*
    方法：回溯搜索算法 + 数组排序 + 同层剪枝
    思路：使用回溯算法遍历决策树，穷举所有解，决策树的每个节点维护当前已选路径track/path和选择列表等信息
          相比t078-子集（不包含重复元素），本题可能包含重复元素，若不进行剪枝处理，子集可能出现重复。
          （1）数组排序：对原始数组进行排序，保证重复元素必相邻，方便后续剪枝
          （2）同层剪枝：当决策树由【当前层】向【下一层】递归时，依次向路径中添加1个数组元素；
                        同一层中，若向不同路径添加重复元素（排序后重复元素相邻），该枝干出现重复，需进行剪枝 → 跳过当次循环。
    时间复杂度：
    空间复杂度：
    类似题目：t046-全排列、t077-组合、t078-子集（不包含重复元素）
             【t040-组合总和II】（数组元素可能有重复，每个元素仅能选一次）
    优化点：路径track/path可使用栈Stack，可方便使用压栈push()和出栈操作pop()。
*/

import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;

public class Solution {
    //结果集
    List<List<Integer>> res = new ArrayList<>();

    public List<List<Integer>> subsetsWithDup(int[] nums) {
        //特判
        if(nums.length == 0) return res;
        //对数组元素进行排序，保证重复元素必相邻，方便后续剪枝
        Arrays.sort(nums);

        //记录已作选择（路径）
        List<Integer> track = new ArrayList<>();
        //调用回溯函数
        backtrack(nums, 0, track);
        return res;
    }

    //回溯函数
    //路径：已作出的选择-track已包含的数组元素
    //选择列表：当前可选择的数组元素（数组nums中start索引及之后的元素）
    //结束条件：正向遍历至数组的末尾时
    private void backtrack(int[] nums, int start, List<Integer> track) {
        //结果集中包含已选路径（部分子集），需对引用track进行拷贝
        res.add(new ArrayList<>(track));

        //遍历数组
        //结束条件：i == nums.length时终止，遍历完全部数组元素
        for(int i = start; i < nums.length; i++){
            //同层剪枝：同一层的两条不同路径中加入的元素出现重复时（数组已排序） → 跳过当次循环
            if(i > start && nums[i] == nums[i - 1]){  // i-1元素的索引必须在start索引及之后位置，即i >= start + 1;
                continue;
            }
            //作出选择
            track.add(nums[i]);
            //递归调用回溯函数 → 进入决策树的下一层（第i + 1个数组元素）
            backtrack(nums, i + 1, track);
            //撤销选择
            track.remove(track.size()-1);
        }
    }
}

rhb_blog

Algorithm__回溯算法

回溯