78&90. 子集&子集 II(回溯法)

>>强大,10k+点赞的 SpringBoot 后台管理系统竟然出了详细教程!

本题来自 LeetCode:78. 子集[1]

78. 子集

题目描述

给定一组不含重复元素的整数数组nums,返回该数组所有可能的子集(幂集)。
说明:解集不能包含重复的子集。
示例:

输入: nums = [1,2,3]
输出:
[
[3],
  [1],
  [2],
  [1,2,3],
  [1,3],
  [2,3],
  [1,2],
  []
]

题目分析

  1. 先看下子集的相关概念:设全集I的元素个数为n,它的子集个数为2^n,真子集的个数为(2^n)-1,非空真子集的个数为(2^n)-2
  2. 由于不包含重复元素,因此本题就是求子集的个数;
  3. 本题比较简单,可以采用回溯法,对于任一一个元素要么存在于子集中,要么不存在于子集中;

题目解答

解法一

class Solution {
public List<List<Integer>> subsets(int[] nums) {
List<List<Integer>> lists = new LinkedList<>();
backtracing(lists, new LinkedList<>(), nums, 0);
return lists;
}

/**
*
* @param lists 子集集合
* @param list 当前子集
* @param nums 数组
* @param index 当前处理的数的下标
*/

public void backtracing(List<List<Integer>> lists,
List<Integer> list,
int[] nums,
int index)
{
if (index == nums.length) {
lists.add(new LinkedList<>(list));
return;
}
// nums[index]不加入子集的情况
backtracing(lists, list, nums, index + 1);
list.add(nums[index]);
// nums[index]加入子集的情况
backtracing(lists, list, nums, index + 1);
list.remove(list.size() - 1);
}
}

复杂度分析:
时间复杂度:O(2^n)
空间复杂度:O(n)

解法二

class Solution {
public List<List<Integer>> subsets(int[] nums) {
List<List<Integer>> lists = new LinkedList<>();
backtracing(lists, new LinkedList<>(), nums, 0);
return lists;
}

/**
*
* @param lists 子集集合
* @param list 当前子集
* @param nums 数组
* @param index 当前处理的数的下标
*/

public void backtracing(List<List<Integer>> lists,
List<Integer> list,
int[] nums,
int index)
{
// nums[index]不加入子集的情况
lists.add(new LinkedList<>(list));
// nums[index]加入子集的情况
for(int i = index; i < nums.length; i ++) {
list.add(nums[i]);
backtracing(lists, list, nums, i + 1);
list.remove(list.size() - 1);
}
}
}

复杂度分析:
时间复杂度:O(n!)
空间复杂度:O(n)

90. 子集 II

本题来自 LeetCode:90. 子集 II[2]

题目详情

给定一个可能包含重复元素的整数数组 nums,返回该数组所有可能的子集(幂集)。
说明:解集不能包含重复的子集。
示例:

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

题目分析

本题和78. 子集最大的不同在于,数组nums可包含重复元素,但是子集集合中不能包含重复的子集
首先来看一下包含重复元素的子集情况,定义数组[2, 2, 2],它的不包含重复的子集的集合,可以直接枚举出来:

[]
[2]
[2, 2]
[2, 2, 2]

从上可以发现规律,n个相等的元素k,其不重复的组合就是其个数的组合,子集分别为0个k1个k...n个k
因此需要对重复的元素单独求子集集合。

题目解答

class Solution {
public List<List<Integer>> subsetsWithDup(int[] nums) {
List<List<Integer>> lists = new LinkedList<>();
// 数组排序,让重复的元素相邻,便于操作
Arrays.sort(nums);
backtracing(lists, new LinkedList<>(), nums, 0);
return lists;
}
/**
*
* @param lists 子集集合
* @param list 当前子集
* @param nums 数组
* @param index 当前处理的数的下标
*/

public void backtracing(List<List<Integer>> lists,
List<Integer> list,
int[] nums,
int index)
{
if (index == nums.length) {
lists.add(new LinkedList<>(list));
return;
}
// 找到值等于nums[index]的区间[index, lastIndex]
int lastIndex = index;
while(lastIndex + 1 < nums.length && nums[index] == nums[lastIndex + 1]) {
lastIndex ++;
}
// nums[index]不加入子集的情况
backtracing(lists, list, nums, lastIndex + 1);
// nums[index]在子集中出现的次数在范围[1, lastIndex + 1]时
for(int i = index; i < lastIndex + 1; i ++) {
list.add(nums[index]);
backtracing(lists, list, nums, lastIndex + 1);
}
// 将元素nums[index]全部移出
for(int i = index; i < lastIndex + 1; i++) {
list.remove(list.size() - 1);
}
}
}

以上解法没有用变量lastIndex=lastIndex + 1 替代lastIndex + 1,是为了更好地理解边界nums[lastIndex] = nums[index],也就是说nums区间[index, lastIndex]的值都等于nums[index]
lastIndex + 1可能等于nums.length,也可能nums[lastIndex + 1] > nums[index]

复杂度分析:
时间复杂度:O(2^n)
空间复杂度:O(n)

参考资料

[1]

78. 子集: https://leetcode-cn.com/problems/subsets/

[2]

90. 子集 II: https://leetcode-cn.com/problems/subsets-ii


原文始发于微信公众号(xiaogan的技术博客):78&90. 子集&子集 II(回溯法)