刷题日记05《回溯算法》

朱雀 2024-03-17 14:44 56阅读 0赞

## 问题描述 ##

[力扣![icon-default.png_t_N5K3][]https://leetcode.cn/problems/TVdhkn/][icon-default.png_t_N5K3_https_leetcode.cn_problems_TVdhkn]

> **给定一个整数数组 nums ，数组中的元素 互不相同 。返回该数组所有可能的子集（幂集）。**
> 
> **解集 不能 包含重复的子集。你可以按 任意顺序 返回解集。**
> 
> **示例 1：**
> 
> **输入：nums = \[1,2,3\]  
> 输出：\[\[\],\[1\],\[2\],\[1,2\],\[3\],\[1,3\],\[2,3\],\[1,2,3\]\]  
> 示例 2：**
> 
> **输入：nums = \[0\]  
> 输出：\[\[\],\[0\]\]**
> 
> **提示：**
> 
>  *  `1 <= nums.length <= 10`
>  *  `-10 <= nums[i] <= 10`
>  *  `nums` 中的所有元素 **互不相同**

## 解题思路 ##

> **回溯问题的经典应用：求一个队列的子集合，要求子集合中不同顺序相同数字的集合也被认为是相同的集合。我们要面对的第一个问题是：如何保证我们最终的求解问题中不包含重复的集合呢？我使用的方法是：使用队列中数字的相对位置，即不改变队列中的相对位置，跳跃性的选择当前位置是否加入目标队列，接下来我们讲解整体思路:设置下标，从第一个数字开始，每一个数字都有加入和不加入目标队列两种选择，当下标指向最后一个元素后方时，将当前数据集加入结果队列即可（这样也保证了数字间的相对位置:只能从前往后进行选择）**

## 实例代码 ##

class Solution {
        private LinkedList<List<Integer>>res=new LinkedList<>();
        private LinkedList<Integer>data=new LinkedList<>();
        public List<List<Integer>> subsets(int[] nums) {
            reverse(nums,0);
            return res;
        }
        public void reverse(int[]nums,int index){
            //递归出口
            if(index==nums.length){
                res.add(new ArrayList(data));
                return ;
            }
            //先递归没有下标的
            reverse(nums,index+1);
            data.addLast(nums[index]);
            reverse(nums,index+1);
            //回溯
            data.removeLast();
    
        }
    }

> **时间复杂度O(N\*2^N) 空间复杂度：O（N）**

## 问题描述 ##

> **给定两个整数 n 和 k，返回 1 ... n 中所有可能的 k 个数的组合。**

示例 1:

> **输入: n = 4, k = 2  
> 输出:  
> \[  
> \[2,4\],  
> \[3,4\],  
> \[2,3\],  
> \[1,2\],  
> \[1,3\],  
> \[1,4\],  
> \]  
> 示例 2:**
> 
> **输入: n = 1, k = 1  
> 输出: \[\[1\]\]**  
> 
> 
> **提示:**
> 
> **1 <= n <= 20  
> 1 <= k <= n**

## 解题思路 ##

> **与上题思路完全一致，但是需要在最后的终止条件时判断是否满足了当前个数，如果满足则加入目标队列，不满足则无需加入**

## 实例代码 ##

class Solution {
        private List<List<Integer>>res=new LinkedList<>();
        private LinkedList<Integer>data=new LinkedList<>();
        public List<List<Integer>> combine(int n, int k) {
            //创建数组
            int[]arr=new int[n];
            for(int i=1;i<=n;++i){
                arr[i-1]=i;
            }
            //调用函数
            reverse(0,arr,k);
            return res;
        }
        public void reverse(int index,int[]arr,int k){
            //递归出口
            if(index==arr.length){
                if(data.size()==k){
                    res.add(new LinkedList(data));
                }
                return;
            }
            //进行递归
            reverse(index+1,arr,k);
            data.addLast(arr[index]);
            reverse(index+1,arr,k);
            //回溯
            data.removeLast();
        }
    
    }

![847e65cf17fd4ef3be57a6c2216bbb06.png][]

[icon-default.png_t_N5K3]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/15/d2251537ecc3425da55f2218b2d5ebc9.png
[icon-default.png_t_N5K3_https_leetcode.cn_problems_TVdhkn]: https://leetcode.cn/problems/TVdhkn/
[847e65cf17fd4ef3be57a6c2216bbb06.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/15/ff3da06ea0fc47028aad710a7eccf2f6.png