LeetCode算法题14：递归和回溯2

文章目录

• 前言
• 
  

  一、全排列II

• • 仿照全排列（n 叉树）
  • 剪枝(去掉重复的结果)
• 
  

  二、组合总和

• • 
    

    一、初始解法（n 叉树）：

  • • 1，采用 Set 去重
    • 2，在递归搜索的时候去重（推荐解法）
    • • 初始解法的遍历过程：
      • 新方式的遍历过程：
    • 引申（组合问题）
    • • 组合问题的解法-n 叉树
      • 组合问题的解法-二叉树
      • 组合问题总结
  • 
    

    二、另一种解法（二叉树）：

• 
  

  三、组合总和II

• • 解法1（n 叉树）
  • 解法2（二叉树）
• 
  

  四、子集

• • 解法1（二叉树）
  • 解法2（n 叉树）
• 
  

  五、子集II

• • 解法1（二叉树）
  • 解法2（n 叉树）
• 总结

---

前言

      递归和回溯续：包括有全排列II 、组合总和、组合总和II、子集、子集II、第 k 个排列、复原IP地址。

一、全排列II

      题目链接：https://leetcode-cn.com/problems/permutations-ii/

      题目描述：给定一个可包含重复数字的序列 nums ，按任意顺序 返回所有不重复的全排列。

仿照全排列（n 叉树）

      和之前的全排列相比，这里的区别是数字序列包含了重复元素。

一个很无脑的方法是将之间全排列解法中的 List 转换为 Set，去掉最后排列结果中的重复序列即可。

参考算法如下：

	LinkedList<Integer> tmp=new LinkedList<>();
    Set<List<Integer>> ans=new HashSet<>();//改为 Set 存储
    boolean[] flag;
    public List<List<Integer>> permuteUnique(int[] nums) {
        int len=nums.length;
        flag=new boolean[len];//由于每次选择一个元素之后，该元素就不能再被选取了，所以需要标记状态
        
        solve(nums,len-1);
        return new ArrayList<>(ans);
    }
    public void solve(int[] nums,int end) {
        if(tmp.size()==end+1){//得到一次排列时，保存结果
            ans.add(new LinkedList<>(tmp));
            return;
        }
        for(int i=0;i<=end;i++){//依次选择每一个元素，由于有标记数组存在，所以此处循环每次都从下标 0 开始。


            if(flag[i]==false){
                tmp.addLast(nums[i]);
                flag[i]=true;
                solve(nums,end);
                flag[i]=false;
                tmp.removeLast();
            }
        }
    }

剪枝(去掉重复的结果)

      以数字序列 【1 1 3】为例，仿照之前的全排列构建回溯过程的选择树如下：

初始集合为空
第一轮选择一个元素	1		1		3
第二轮选择第二个元素	1 1	1 3	1 1	1 3	3 1	3 1
第三轮选择第三个元素	1 1 3	1 3 1	1 1 3	1 3 1	3 1 1	3 1 1

      可以发现重复的结果出现在：第一轮中选择第二个 1 得到的最终结果和第一个 1 是一模一样的，均为 【1 1 3】和【1 3 1】；在第一轮选择 3 的情况下，第二轮的两次选择都是 1，最终结果也产生了重复。

      所以剪枝的条件，也即约束条件为：当数组采用升序排列时，如果出现当前元素和上一个元素相等时，就没有必要继续递归遍历了；但这还不够，这样在第二轮就永远不会出现【1 1】序列了。

如果第一个 1 被选取了之后，第二个 1 也被选取，这是重复结果的第一次出现，这种情况应该被允许发生；对应的重复结果的第二次出现就不允许发生了，比如在第一轮选择第二个 1 时，第一个 1 未被选取（状态为 false）,由于之后的递归遍历得到的都是重复结果，所以这种情况跳过（剪枝）。

      所以给出的剪枝条件（约束条件）为：

if(i>0&&(nums[i]==nums[i-1])&&flag[i-1]==false)
	continue;

      它表示的含义为：仅允许重复的排列结果第一次出现，后面会重复出现的递归遍历被跳过（剪去）。

      参考算法如下：

	LinkedList<Integer> tmp=new LinkedList<>();
    List<List<Integer>> ans=new LinkedList<>();
    boolean[] flag;
    public List<List<Integer>> permuteUnique(int[] nums) {
        int len=nums.length;
        flag=new boolean[len];//由于每次选择一个元素之后，该元素就不能再被选取了，所以需要标记状态
        Arrays.sort(nums);
        solve(nums,len-1);
        return ans;
    }
    public void solve(int[] nums,int end) {
        if(tmp.size()==end+1){//得到一次排列时，保存结果
            ans.add(new LinkedList<>(tmp));
            return;
        }
        for(int i=0;i<=end;i++){//依次选择每一个元素，由于有标记数组存在，所以此处循环每次都从下标 0 开始。


            if(flag[i]==false){
                if(i>0&&(nums[i]==nums[i-1])&&flag[i-1]==false)
                    continue;
                tmp.addLast(nums[i]);
                flag[i]=true;
                solve(nums,end);
                flag[i]=false;
                tmp.removeLast();
            }
        }
    }

      虽说约束条件改为 if(i>0&&(nums[i]==nums[i-1])&&flag[i-1]) 也是可以的，它保存的是重复排列的最后一次出现结果，它和保存第一次出现结果正好相反，并且也不太好理解，不建议采用这种做法。

二、组合总和

      题目链接：https://leetcode-cn.com/problems/combination-sum/
      题目描述：给你一个 无重复元素 的整数数组 candidates 和一个目标整数 target ，找出 candidates 中可以使数字和为目标数 target 的 所有 不同组合 ，并以列表形式返回。

你可以按 任意顺序 返回这些组合。

candidates 中的 同一个 数字可以 无限制重复被选取 。

如果至少一个数字的被选数量不同，则两种组合是不同的。

对于给定的输入，保证和为 target 的不同组合数少于 150 个。

一、初始解法（n 叉树）：

      直接干：

    List<List<Integer>> ans=new ArrayList<>();
    List<Integer> tmp=new LinkedList<>();
    public List<List<Integer>> combinationSum(int[] candidates, int target) {
        Arrays.sort(candidates);
        solve(candidates,target);//先排序
        return ans;
    }
    void solve(int[] candi,int target){
        if(target==0){
            ans.add(new LinkedList<>(tmp));
            return;
        }

        for(int i=0;i<candi.length;i++){
            if(candi[i]>target)
                break;//由于已经按照升序排序了，直接break即可。


            tmp.add(candi[i]);
            solve(candi,target-candi[i]);
            tmp.remove(tmp.size()-1);
        }
    }

      然而初始解法的答案存在重复情况，对于示例 candidates = [2,3,6,7], target = 7，此解法的答案为：[2, 2, 3] [2, 3, 2] [3, 2, 2] [7]，这是由于在搜索过程产生了重复，具体的可以仿照上一题画出递归树来比对。

关于如何去重有两种方法：

1，采用 Set 去重

      参考代码如下：（缺点是效率太慢，勉强能用）

	Set<List<Integer>> ans=new HashSet<>();
    List<Integer> tmp=new LinkedList<>();
    public List<List<Integer>> combinationSum(int[] candidates, int target) {
        Arrays.sort(candidates);
        solve(candidates,target);
        List<List<Integer>> re=new ArrayList<>();
        for(List l:ans)
            re.add(l);
        return re;
    }
    void solve(int[] candi,int target){
        if(target==0){
            List<Integer> t=new LinkedList<>(tmp);
            Collections.sort(t);//这里需要先排序，从而在添加进集合的时候去重。


            ans.add(t);
            return;
        }

        for(int i=0;i<candi.length;i++){
            if(candi[i]>target)
                break;
            tmp.add(candi[i]);
            solve(candi,target-candi[i]);
            tmp.remove(tmp.size()-1);
        }
    }

2，在递归搜索的时候去重（推荐解法）

      参考文章：https://leetcode-cn.com/problems/combination-sum/solution/hui-su-suan-fa-jian-zhi-python-dai-ma-java-dai-m-2/，本题的去重方式采用的是设置搜索起点。

      初始解法答案为[2, 2, 3] [2, 3, 2] [3, 2, 2] [7]。

约定：第一轮表示选择一个元素的时候，第二轮选择第二个元素，第三轮选择第三个元素，第四轮选择第四个元素。

初始解法的遍历过程：

      当第一轮选择 2 时 ，接下来的遍历为：第二轮选2、3、6、7。

… 第三轮选2、3、6、7。

… 第四轮选2、3、6、7。

…

      当第一轮选择 3 时，要么还是按照之前的遍历思路（第二轮选2、3、6、7；… 第三轮选2、3、6、7；… 第四轮选2、3、6、7 …），要么就舍弃第一轮已经选过的 2，新的遍历方式（第二轮选3、6、7；… 第三轮选3、6、7；… 第四轮选3、6、7 …）。

新方式的遍历过程：

      okk，感觉这样好像有点合理哈，因为我们的目的是求一些元素的组合，而新的遍历方式并不会漏掉任何组合方式。

也刚好解决了初始解法中重复问题（能够轻易的发现[3, 2, 2]被排除掉了）。

      当第一轮选择 2 时，第二轮选择2、3、6、7，第三轮选择 2、3、6、7，第四轮 2、3、6、7时：目标集合[2, 2, 3]表示第一轮选择 2 、第二轮选择 2 、第三轮选择 3 ；继续执行直到状态为：第一轮选择 2 、第二轮选择 3 时。

      如果按照旧的遍历方式，第三轮仍然选 2，得到了重复集合[2, 3, 2]。

但是按照新的遍历方式，在第二轮选择 3 时，第三轮也会从 3 开始选择，所以在此也跳过了重复的集合选取，[2, 3, 2]就会被排除掉了。

      由此可得到的算法参考如下：（采用 begin 变量标记遍历的起点下标）

	List<List<Integer>> ans=new ArrayList<>();
    List<Integer> tmp=new LinkedList<>();
    public List<List<Integer>> combinationSum(int[] candidates, int target) {
        Arrays.sort(candidates);
        solve(candidates,target,0);
        return ans;
    }
    void solve(int[] candi,int target,int begin){
        if(target==0){
            ans.add(new LinkedList<>(tmp));
            return;
        }

        for(int i=begin;i<candi.length;i++){
            if(candi[i]>target)
                break;
            tmp.add(candi[i]);
            solve(candi,target-candi[i],i);//一旦到了下标i处，打死也不会选择 下标小于i处 的元素了
            tmp.remove(tmp.size()-1);
        }
    }

引申（组合问题） 组合问题的解法-n 叉树

       参考上面的新遍历方式的代码可以得到的一种求组合（在candidates中求 k 个数的组合）的解法如下：

	List<List<Integer>> ans=new ArrayList<>();
    List<Integer> tmp=new LinkedList<>();
    public List<List<Integer>> combine(int[] candidates, int k) {
        solve(candidates,k,0);
        return ans;
    }
    void solve(int[] candi,int k,int begin){
        if(tmp.size()==k){
            ans.add(new LinkedList<>(tmp));
            return;
        }

        for(int i=begin;i<candi.length;i++){
        	if(tmp.size()+candi.length-i)<k)	
        		break; //这里添加了剪枝条件
            tmp.add(candi[i]);
            solve(candi,k,i+1);//此处同上，选择了 i 处元素之后之后就不会选择下标小于等于i处的元素了
            tmp.remove(tmp.size()-1);
        }
    }

组合问题的解法-二叉树

      参考博客：https://blog.csdn.net/Little_ant_/article/details/123676777，代码如下：

    List<List<Integer>> ans=new LinkedList<>();
    List<Integer> tmp=new LinkedList<>();
    public List<List<Integer>> combine(int n, int k) {
        solve(1,n,k);
        return ans;
    }
    public void solve(int cur,int end,int k){
        if(tmp.size()+(end-cur+1)<k)
            return;

        if(tmp.size()==k){ //碰到每一种成功的情况时应该保存                      
            ans.add(new LinkedList<>(tmp));
            return;
        }

        tmp.add(cur); //选取当前 cur 的情况								  
        solve(cur+1,end,k);
        tmp.remove(tmp.size()-1); //不选取的情况
        solve(cur+1,end,k);
    }

组合问题总结

      解法1 如下面的二叉树来示意 （n=4，k=2）：（不想画图，凑合一看）
                                                                        【 】
                                          【1】                                                                【】
                                 【1,2】    【1】                                           【2】                                         【】
                                         【1,3】    【1】                           【2,3】    【2】                  【3】                  【】
                                                  【1,4】   【1】                              【2,4]    【2】    【3,4】 【3】    【4】   【】
      解法2 如下面的 n 叉树所示意：
                                                                                                    【 】
                                          【1】                                          【2】                          【3】            【4】
                         【1,2】    【1,3】     【1,4】           【2,3】      【2,4】                【3,4】
      以上两种示意图对应两种不同的解法思路。

务必领会！

二、另一种解法（二叉树）：

      组合问题解法1的思路参考上图，本题也可以采用类似的方式，直接上代码：

	List<List<Integer>> ans=new ArrayList<>();
    List<Integer> tmp=new LinkedList<>();
    public List<List<Integer>> combinationSum(int[] candidates, int target) {
        Arrays.sort(candidates);
        solve(candidates,target,0);
        return ans;
    }
    void solve(int[] candi,int target,int cur){//cur 为当前元素的下标
        if(target==0){
            ans.add(new LinkedList<>(tmp));
            return;
        }
        if(cur==candi.length)//退出条件1
            return;
        if(candi[cur]>target)//退出条件2
            return;
        //选择当前元素，target减小，cur由题意可知，应不变。

    
        tmp.add(candi[cur]);
        solve(candi,target-candi[cur],cur);
        //不选择当前元素，target不变，cur应加一。


        tmp.remove(tmp.size()-1);
        solve(candi,target,cur+1);
    }

      这种解法不会造成有重复结果。

因为，一个 solve 中的下标为 start，另一个 solve 中的下标为 start+1，这也表明了，一旦访问到下标 start 处，就再也不会遇到下标小于 start 的元素了。

这和初始解法中的推荐解法含义是一样的（用 begin 变量标记下一轮起始元素）

      对应的代码为（稍加修改后）：

    LinkedList<Integer> tmp=new LinkedList<>();
    List<List<Integer>> ans=new LinkedList<>();
    boolean[] flag;
    public List<List<Integer>> permute(int[] nums) {
        int len=nums.length;
        flag=new boolean[len];//由于每次选择一个元素之后，该元素就不能再被选取了，所以需要标记状态
        
        solve(nums,len-1);
        return ans;
    }
    public void solve(int[] nums,int end) {
        if(tmp.size()==end+1){//得到一次排列时，保存结果
            ans.add(new LinkedList<>(tmp));
            return;
        }
        for(int i=0;i<=end;i++){//依次选择每一个元素，由于有标记数组存在，所以此处循环每次都从下标 0 开始。


            if(flag[i]==false){
                tmp.addLast(nums[i]);
                flag[i]=true;
                solve(nums,end);
                flag[i]=false;
                tmp.removeLast();
            }
        }
    }

三、组合总和II

      题目链接：https://leetcode-cn.com/problems/combination-sum-ii/

      题目描述：给定一个候选人编号的集合 candidates 和一个目标数 target ，找出 candidates 中所有可以使数字和为 target 的组合。

candidates 中的每个数字在每个组合中只能使用 一次 。

注意：解集不能包含重复的组合。

解法1（n 叉树）

      初始代码为：

	List<List<Integer>> ans=new ArrayList<>();
    List<Integer> tmp=new LinkedList<>();
    public List<List<Integer>> combinationSum2(int[] candidates, int target) {
        Arrays.sort(candidates);
        solve(candidates,target,candidates.length,0);
        return ans;
    }
    public void solve(int[] c,int target,int len,int begin){
        if(target==0){
            ans.add(new LinkedList<>(tmp));
            return;
        }
        for(int i=begin;i<len;i++){
            if(c[i]>target)
                break;  //这里和前面的 sort 对应，如果不排序的话应该为 continue
            tmp.add(c[i]);
            solve(c,target-c[i],len,i+1);//i+1表示不对当前元素重复选取。


            tmp.remove(tmp.size()-1);
        }
    }

      但仍会造成重复，重复的原因在于 candidates 数组中本身存在重复元素，比如：[10,1,2,7,6,1,5] ，这里有两个 1 存在。

那么如何剪枝去重呢？这里可以先画一画递归搜索树，对 candidates 排完序之后，两个 1 接连排列，在初始代码中：前面那个 1 的搜索空间包含了后面那个 1 的搜索空间，这就是重复发生的原因。

解决方法：如果前面那个 1 搜索结束之后，那么后面那个 1 直接跳过，在同一层中的重复数字永远只取第一个。

这一点和 全排列II 剪枝非常类似。

得到了最终代码如下：

	List<List<Integer>> ans=new ArrayList<>();
    List<Integer> tmp=new LinkedList<>();
    public List<List<Integer>> combinationSum2(int[] candidates, int target) {
        Arrays.sort(candidates);
        boolean[] visited=new boolean[candidates.length];//新加入 visited 数组
        solve(candidates,target,candidates.length,0,visited);
        return ans;
    }
    public void solve(int[] c,int target,int len,int begin,boolean[] visited){
        if(target==0){
            ans.add(new LinkedList<>(tmp));
            return;
        }
        for(int i=begin;i<len;i++){//如果一个 1 被遍历完之后，其他 1 也不能被访问了。


            if(c[i]>target)
                break;
            if(i>0&&c[i]==c[i-1]&&visited[i-1]==false)//false 表示重复元素的第一个已遍历结束，后面的重复元素都需要跳过
                continue;
            visited[i]=true;
            tmp.add(c[i]);
            solve(c,target-c[i],len,i+1,visited);
            tmp.remove(tmp.size()-1);
            visited[i]=false;
        }
    }

      补充：上述代码将 if(i>0&&c[i]==c[i-1]&&visited[i-1]==false) continue; 修改成为 if (i > begin && candidates[i] == candidates[i - 1]) continue; ，也会具有相同的作用。

解法2（二叉树）

      初始代码为：

	List<List<Integer>> ans=new ArrayList<>();
    List<Integer> tmp=new LinkedList<>();
    public List<List<Integer>> combinationSum2(int[] candidates, int target) {
        Arrays.sort(candidates);
        solve(candidates,target,candidates.length,0);
        return ans;
    }
    public void solve(int[] c,int target,int len,int cur){
        if(target==0){
            ans.add(new LinkedList<>(tmp));
            return;
        }
        if(cur==len)
            return;
        if(c[cur]>target)
            return;
        tmp.add(c[cur]);
        solve(c,target-c[cur],len,cur+1);
        tmp.remove(tmp.size()-1);
        solve(c,target,len,cur+1);
        
    }

      需要去重，保证在同一层中的相同元素永远只取第一个。

最终代码如下：

	List<List<Integer>> ans=new ArrayList<>();
    List<Integer> tmp=new LinkedList<>();
    public List<List<Integer>> combinationSum2(int[] candidates, int target) {
        Arrays.sort(candidates);
        solve(candidates,target,candidates.length,0);
        return ans;
    }
    public void solve(int[] c,int target,int len,int cur){
        if(target==0){
            ans.add(new LinkedList<>(tmp));
            return;
        }
        if(cur==len)// 退出条件1
            return;
        if(c[cur]>target)// 退出条件2
            return;

        tmp.add(c[cur]);
        solve(c,target-c[cur],len,cur+1);

        int a=tmp.get(tmp.size()-1),i;//若当前层有重复元素，那 a 为第一个，并且此处 a 已经被使用过了
        tmp.remove(tmp.size()-1);
        for(i=cur+1;i<len;i++)//同一层的下一个元素值不能为 a 了，
            if(c[i]!=a)
                break;

        solve(c,target,len,i);
    }

四、子集

      题目链接：https://leetcode-cn.com/problems/subsets/

      题目描述：给你一个整数数组 nums ，数组中的元素 互不相同 。

返回该数组所有可能的子集（幂集）。

解集 不能 包含重复的子集。

你可以按 任意顺序 返回解集。

解法1（二叉树）

      求集合的子集，本题需要熟悉二叉递归搜索树，因为该树的所有叶子结点就是本题的答案，将所有叶子结点加入到集合并返回。

当 nums = { 1, 2, 3 }；时，该树如下图所示（画图有点累…）：

      代码如下：

	List<List<Integer>> ans=new LinkedList<>();
    Deque<Integer> tmp=new LinkedList<>();
    public List<List<Integer>> subsets(int[] nums) {
        solve(nums,0);
        return ans;
    }
    public void solve(int[] nums,int cur){
        if(cur==nums.length){
            ans.add(new LinkedList<>(tmp));
            return;
        }
        tmp.add(nums[cur]);
        solve(nums,cur+1);
        tmp.removeLast();
        solve(nums,cur+1);
    }

解法2（n 叉树）

      同理，n 叉递归搜索树的所有结点是本题的答案，所有结点加入集合直接返回即可。

当 nums = { 1, 2, 3 }；时，该树如下图所示：

      代码如下：

	List<List<Integer>> ans=new LinkedList<>();
    Deque<Integer> tmp=new LinkedList<>();
    public List<List<Integer>> subsets(int[] nums) {
        solve(nums,0);
        return ans;
    }
    public void solve(int[] nums,int begin){
        ans.add(new LinkedList<>(tmp));

        for(int i=begin;i<nums.length;i++){
            tmp.add(nums[i]);
            solve(nums,i+1);
            tmp.removeLast();
        }
    }

五、子集II

      题目链接：https://leetcode-cn.com/problems/subsets-ii/

      题目描述：给你一个整数数组 nums ，其中可能包含重复元素，请你返回该数组所有可能的子集（幂集）。

解集 不能 包含重复的子集。

返回的解集中，子集可以按 任意顺序 排列。

解法1（二叉树）

      在上题的基础上去重即可，代码如下：

	List<List<Integer>> ans=new LinkedList<>();
    Deque<Integer> tmp=new LinkedList<>();
    public List<List<Integer>> subsetsWithDup(int[] nums) {
        Arrays.sort(nums);//含有重复元素要记得排序哦。


        solve(nums,0);
        return ans;
    }
    public void solve(int[] nums,int cur){
        if(cur==nums.length){
            ans.add(new LinkedList<>(tmp));
            return;
        }
        tmp.add(nums[cur]);
        solve(nums,cur+1);

        int a=tmp.peekLast(),i;
        tmp.removeLast();
        for(i=cur+1;i<nums.length;i++)
            if(nums[i]!=a)
                break;

        solve(nums,i);
    }

解法2（n 叉树）

      同理，代码如下：

	List<List<Integer>> ans=new LinkedList<>();
    Deque<Integer> tmp=new LinkedList<>();
    public List<List<Integer>> subsetsWithDup(int[] nums) {
        Arrays.sort(nums);
        solve(nums,0);
        return ans;
    }
    public void solve(int[] nums,int begin){
        ans.add(new LinkedList<>(tmp));

        for(int i=begin;i<nums.length;i++){
            if(i>begin&&nums[i]==nums[i-1])//如果有重复元素，只会在其第一次出现时选取
                continue;
            tmp.add(nums[i]);
            solve(nums,i+1);
            tmp.removeLast();
        }
    }

      采用标记数组的代码如下：

List<List<Integer>> ans=new LinkedList<>();
    Deque<Integer> tmp=new LinkedList<>();
    public List<List<Integer>> subsetsWithDup(int[] nums) {
        Arrays.sort(nums);
        boolean[] visited=new boolean[nums.length];
        solve(nums,0,visited);
        return ans;
    }
    public void solve(int[] nums,int begin,boolean[] visited){
        ans.add(new LinkedList<>(tmp));

        for(int i=begin;i<nums.length;i++){
            if(i>0&&nums[i]==nums[i-1]&&visited[i-1]==false)
                continue;
            visited[i]=true;
            tmp.add(nums[i]);
            solve(nums,i+1,visited);
            tmp.removeLast();
            visited[i]=false;
        }
    }

总结

      未完