算法-回溯-求子集2

缺乏、安全感 2023-05-21 08:59 51阅读 0赞

# 算法-回溯-求子集2 #

# 1 题目概述 #

## 1.1 题目出处 ##

https://leetcode-cn.com/problems/subsets-ii/

## 1.2 题目描述 ##

给定一个可能包含重复元素的整数数组 nums，返回该数组所有可能的子集（幂集）。

说明：解集不能包含重复的子集。

示例:

输入: [1,2,2]
    输出:
    [
      [2],
      [1],
      [1,2,2],
      [2,2],
      [1,2],
      []
    ]

# 2 回溯法 #

## 2.1 思路 ##

和[算法-回溯/位运算-求子集][-_-]类似，只不过需要剔除相同的组合。

## 2.2 代码 ##

class Solution { 
        public List<List<Integer>> subsetsWithDup(int[] nums) { 
            List<List<Integer>> resultList = new ArrayList<>();
            if(null == nums || nums.length == 0){ 
                return resultList;
            }
            Arrays.sort(nums);
            backtrack(nums, resultList, new ArrayList<Integer>(), 0);
            return resultList;
        }
        private void backtrack(int[] nums, List<List<Integer>> resultList, ArrayList<Integer> prevList, int start){ 
            if(!resultList.contains(prevList)){ 
                resultList.add(new ArrayList(prevList));
            }
            if(prevList.size() == nums.length){ 
                return;
            }
            for(int j = start; j < nums.length; j++){ 
                prevList.add(nums[j]);
                backtrack(nums, resultList, prevList, j + 1);
                prevList.remove(prevList.size() - 1);
            }
        }
    }

## 2.3 时间复杂度 ##

O(N \* 2^N)

*  排序原始数组  
    O(N log(N))
 *  复制  
    O(N \* 2^N)。
    
    每次回溯递归都需要复制一个(N)的List对象，总共`2^N`个组合需要递归（N个数的全子集数量就是`2^N`）
 *  每次递归都需要判断resultList是否包含prevList  
    O(N \* 2^N)

实际体验超级慢

## 2.4 空间复杂度 ##

O(N \* 2^N)

*  每次回溯递归都需要创建一个List对象，总共N \* 2^N个

# 3 优化的回溯法 #

## 3.1 思路 ##

上面的回溯法执行耗时16ms，超级慢。

看了下代码，执行`resultList.contains(prevList)`的时候需要遍历`resultList`中的所有子list，然后挨个遍历子list和本prevList所有元素是否相同。。。这也太慢了。

想想，怎么去重？那就是backtract遍历的时候如果和该次遍历中出现过的元素相同就不

## 3.2 代码 ##

class Solution { 
        public List<List<Integer>> subsetsWithDup(int[] nums) { 
            List<List<Integer>> resultList = new ArrayList<>();
            if(null == nums || nums.length == 0){ 
                return resultList;
            }
            // 这里必须排序，否则可能造成{1,4} {4,1}这样的重复组合
            Arrays.sort(nums);
            backtrack(nums, resultList, new ArrayList<Integer>(), 0);
            return resultList;
        }
        private void backtrack(int[] nums, List<List<Integer>> resultList, ArrayList<Integer> prevList, int start){ 
            // if(!resultList.contains(prevList)){ 
            resultList.add(new ArrayList(prevList));
            // }
            if(prevList.size() == nums.length){ 
                // 结束条件
                return;
            }
            for(int j = start; j < nums.length; j++){ 
                // 只要和前一个元素相同，就说明此次回溯已经选过，不再选择
                if(j > start && nums[j] == nums[j-1]){ 
                    continue;
                }
                prevList.add(nums[j]);
                backtrack(nums, resultList, prevList, j + 1);
                prevList.remove(prevList.size() - 1);
            }
        }
    }

## 3.3 时间复杂度 ##

O(N \* 2^N)

*  排序原始数组  
    O(N log(N))
 *  复制  
    O(N \* 2^N)。
    
    每次回溯递归都需要复制一个(N)的List对象，总共`2^N`个组合需要递归（N个数的全子集数量就是`2^N`）

这次快多了  
![在这里插入图片描述][20200424145919453.png]

## 3.4 空间复杂度 ##

O(N \* 2^N)

*  每次回溯递归都需要创建一个List对象，总共N \* 2^N个

[-_-]: https://blog.csdn.net/baichoufei90/article/details/105700647
[20200424145919453.png]: /images/20230521/523e3f5e6e524c678f9a53d518b0fb3a.png