参与本项目,贡献其他语言版本的代码,拥抱开源,让更多学习算法的小伙伴们受益!
给定一个可能包含重复元素的整数数组 nums,返回该数组所有可能的子集(幂集)。
说明:解集不能包含重复的子集。
示例:
- 输入: [1,2,2]
- 输出: [ [2], [1], [1,2,2], [2,2], [1,2], [] ]
《代码随想录》算法视频公开课:回溯算法解决子集问题,如何去重?| LeetCode:90.子集II,相信结合视频再看本篇题解,更有助于大家对本题的理解。
做本题之前一定要先做78.子集。
这道题目和78.子集区别就是集合里有重复元素了,而且求取的子集要去重。
那么关于回溯算法中的去重问题,在40.组合总和II中已经详细讲解过了,和本题是一个套路。
剧透一下,后期要讲解的排列问题里去重也是这个套路,所以理解“树层去重”和“树枝去重”非常重要。
用示例中的[1, 2, 2] 来举例,如图所示: (注意去重需要先对集合排序)
从图中可以看出,同一树层上重复取2 就要过滤掉,同一树枝上就可以重复取2,因为同一树枝上元素的集合才是唯一子集!
本题就是其实就是回溯算法:求子集问题!的基础上加上了去重,去重我们在回溯算法:求组合总和(三)也讲过了,所以我就直接给出代码了:
C++代码如下:
class Solution {
private:
vector<vector<int>> result;
vector<int> path;
void backtracking(vector<int>& nums, int startIndex, vector<bool>& used) {
result.push_back(path);
for (int i = startIndex; i < nums.size(); i++) {
// used[i - 1] == true,说明同一树枝candidates[i - 1]使用过
// used[i - 1] == false,说明同一树层candidates[i - 1]使用过
// 而我们要对同一树层使用过的元素进行跳过
if (i > 0 && nums[i] == nums[i - 1] && used[i - 1] == false) {
continue;
}
path.push_back(nums[i]);
used[i] = true;
backtracking(nums, i + 1, used);
used[i] = false;
path.pop_back();
}
}
public:
vector<vector<int>> subsetsWithDup(vector<int>& nums) {
result.clear();
path.clear();
vector<bool> used(nums.size(), false);
sort(nums.begin(), nums.end()); // 去重需要排序
backtracking(nums, 0, used);
return result;
}
};
- 时间复杂度: O(n * 2^n)
- 空间复杂度: O(n)
使用set去重的版本。
class Solution {
private:
vector<vector<int>> result;
vector<int> path;
void backtracking(vector<int>& nums, int startIndex) {
result.push_back(path);
unordered_set<int> uset;
for (int i = startIndex; i < nums.size(); i++) {
if (uset.find(nums[i]) != uset.end()) {
continue;
}
uset.insert(nums[i]);
path.push_back(nums[i]);
backtracking(nums, i + 1);
path.pop_back();
}
}
public:
vector<vector<int>> subsetsWithDup(vector<int>& nums) {
result.clear();
path.clear();
sort(nums.begin(), nums.end()); // 去重需要排序
backtracking(nums, 0);
return result;
}
};
本题也可以不使用used数组来去重,因为递归的时候下一个startIndex是i+1而不是0。
如果要是全排列的话,每次要从0开始遍历,为了跳过已入栈的元素,需要使用used。
代码如下:
class Solution {
private:
vector<vector<int>> result;
vector<int> path;
void backtracking(vector<int>& nums, int startIndex) {
result.push_back(path);
for (int i = startIndex; i < nums.size(); i++) {
// 而我们要对同一树层使用过的元素进行跳过
if (i > startIndex && nums[i] == nums[i - 1] ) { // 注意这里使用i > startIndex
continue;
}
path.push_back(nums[i]);
backtracking(nums, i + 1);
path.pop_back();
}
}
public:
vector<vector<int>> subsetsWithDup(vector<int>& nums) {
result.clear();
path.clear();
sort(nums.begin(), nums.end()); // 去重需要排序
backtracking(nums, 0);
return result;
}
};
其实这道题目的知识点,我们之前都讲过了,如果之前讲过的子集问题和去重问题都掌握的好,这道题目应该分分钟AC。
使用used数组
class Solution {
List<List<Integer>> result = new ArrayList<>();// 存放符合条件结果的集合
LinkedList<Integer> path = new LinkedList<>();// 用来存放符合条件结果
boolean[] used;
public List<List<Integer>> subsetsWithDup(int[] nums) {
if (nums.length == 0){
result.add(path);
return result;
}
Arrays.sort(nums);
used = new boolean[nums.length];
subsetsWithDupHelper(nums, 0);
return result;
}
private void subsetsWithDupHelper(int[] nums, int startIndex){
result.add(new ArrayList<>(path));
if (startIndex >= nums.length){
return;
}
for (int i = startIndex; i < nums.length; i++){
if (i > 0 && nums[i] == nums[i - 1] && !used[i - 1]){
continue;
}
path.add(nums[i]);
used[i] = true;
subsetsWithDupHelper(nums, i + 1);
path.removeLast();
used[i] = false;
}
}
}
不使用used数组
class Solution {
List<List<Integer>> res = new ArrayList<>();
LinkedList<Integer> path = new LinkedList<>();
public List<List<Integer>> subsetsWithDup( int[] nums ) {
Arrays.sort( nums );
subsetsWithDupHelper( nums, 0 );
return res;
}
private void subsetsWithDupHelper( int[] nums, int start ) {
res.add( new ArrayList<>( path ) );
for ( int i = start; i < nums.length; i++ ) {
// 跳过当前树层使用过的、相同的元素
if ( i > start && nums[i - 1] == nums[i] ) {
continue;
}
path.add( nums[i] );
subsetsWithDupHelper( nums, i + 1 );
path.removeLast();
}
}
}
回溯 利用used数组去重
class Solution:
def subsetsWithDup(self, nums):
result = []
path = []
used = [False] * len(nums)
nums.sort() # 去重需要排序
self.backtracking(nums, 0, used, path, result)
return result
def backtracking(self, nums, startIndex, used, path, result):
result.append(path[:]) # 收集子集
for i in range(startIndex, len(nums)):
# used[i - 1] == True,说明同一树枝 nums[i - 1] 使用过
# used[i - 1] == False,说明同一树层 nums[i - 1] 使用过
# 而我们要对同一树层使用过的元素进行跳过
if i > 0 and nums[i] == nums[i - 1] and not used[i - 1]:
continue
path.append(nums[i])
used[i] = True
self.backtracking(nums, i + 1, used, path, result)
used[i] = False
path.pop()
回溯 利用集合去重
class Solution:
def subsetsWithDup(self, nums):
result = []
path = []
nums.sort() # 去重需要排序
self.backtracking(nums, 0, path, result)
return result
def backtracking(self, nums, startIndex, path, result):
result.append(path[:]) # 收集子集
uset = set()
for i in range(startIndex, len(nums)):
if nums[i] in uset:
continue
uset.add(nums[i])
path.append(nums[i])
self.backtracking(nums, i + 1, path, result)
path.pop()
回溯 利用递归的时候下一个startIndex是i+1而不是0去重
class Solution:
def subsetsWithDup(self, nums):
result = []
path = []
nums.sort() # 去重需要排序
self.backtracking(nums, 0, path, result)
return result
def backtracking(self, nums, startIndex, path, result):
result.append(path[:]) # 收集子集
for i in range(startIndex, len(nums)):
# 而我们要对同一树层使用过的元素进行跳过
if i > startIndex and nums[i] == nums[i - 1]:
continue
path.append(nums[i])
self.backtracking(nums, i + 1, path, result)
path.pop()
使用used数组
var (
result [][]int
path []int
)
func subsetsWithDup(nums []int) [][]int {
result = make([][]int, 0)
path = make([]int, 0)
used := make([]bool, len(nums))
sort.Ints(nums) // 去重需要排序
backtracing(nums, 0, used)
return result
}
func backtracing(nums []int, startIndex int, used []bool) {
tmp := make([]int, len(path))
copy(tmp, path)
result = append(result, tmp)
for i := startIndex; i < len(nums); i++ {
// used[i - 1] == true,说明同一树枝candidates[i - 1]使用过
// used[i - 1] == false,说明同一树层candidates[i - 1]使用过
// 而我们要对同一树层使用过的元素进行跳过
if i > 0 && nums[i] == nums[i-1] && used[i-1] == false {
continue
}
path = append(path, nums[i])
used[i] = true
backtracing(nums, i + 1, used)
path = path[:len(path)-1]
used[i] = false
}
}
不使用used数组
var (
path []int
res [][]int
)
func subsetsWithDup(nums []int) [][]int {
path, res = make([]int, 0, len(nums)), make([][]int, 0)
sort.Ints(nums)
dfs(nums, 0)
return res
}
func dfs(nums []int, start int) {
tmp := make([]int, len(path))
copy(tmp, path)
res = append(res, tmp)
for i := start; i < len(nums); i++ {
if i != start && nums[i] == nums[i-1] {
continue
}
path = append(path, nums[i])
dfs(nums, i+1)
path = path[:len(path)-1]
}
}
var subsetsWithDup = function(nums) {
let result = []
let path = []
let sortNums = nums.sort((a, b) => {
return a - b
})
function backtracing(startIndex, sortNums) {
result.push([...path])
if(startIndex > nums.length - 1) {
return
}
for(let i = startIndex; i < nums.length; i++) {
if(i > startIndex && nums[i] === nums[i - 1]) {
continue
}
path.push(nums[i])
backtracing(i + 1, sortNums)
path.pop()
}
}
backtracing(0, sortNums)
return result
};
function subsetsWithDup(nums: number[]): number[][] {
nums.sort((a, b) => a - b);
const resArr: number[][] = [];
backTraking(nums, 0, []);
return resArr;
function backTraking(nums: number[], startIndex: number, route: number[]): void {
resArr.push([...route]);
let length: number = nums.length;
if (startIndex === length) return;
for (let i = startIndex; i < length; i++) {
if (i > startIndex && nums[i] === nums[i - 1]) continue;
route.push(nums[i]);
backTraking(nums, i + 1, route);
route.pop();
}
}
};
set去重版本:
// 使用set去重版本
function subsetsWithDup(nums: number[]): number[][] {
const result: number[][] = [];
const path: number[] = [];
// 去重之前先排序
nums.sort((a, b) => a - b);
function backTracking(startIndex: number) {
// 收集结果
result.push([...path])
// 此处不返回也可以因为,每次递归都会使startIndex + 1,当这个数大到nums.length的时候就不会进入递归了。
if (startIndex === nums.length) {
return
}
// 定义每一个树层的set集合
const set: Set<number> = new Set()
for (let i = startIndex; i < nums.length; i++) {
// 去重
if (set.has(nums[i])) {
continue
}
set.add(nums[i])
path.push(nums[i])
backTracking(i + 1)
// 回溯
path.pop()
}
}
backTracking(0)
return result
};
impl Solution {
fn backtracking(result: &mut Vec<Vec<i32>>, path: &mut Vec<i32>, nums: &Vec<i32>, start_index: usize, used: &mut Vec<bool>) {
result.push(path.clone());
let len = nums.len();
// if start_index >= len { return; }
for i in start_index..len {
if i > 0 && nums[i] == nums[i - 1] && !used[i - 1] { continue; }
path.push(nums[i]);
used[i] = true;
Self::backtracking(result, path, nums, i + 1, used);
used[i] = false;
path.pop();
}
}
pub fn subsets_with_dup(mut nums: Vec<i32>) -> Vec<Vec<i32>> {
let mut result: Vec<Vec<i32>> = Vec::new();
let mut path: Vec<i32> = Vec::new();
let mut used = vec![false; nums.len()];
nums.sort();
Self::backtracking(&mut result, &mut path, &nums, 0, &mut used);
result
}
}
set 去重版本
use std::collections::HashSet;
impl Solution {
pub fn subsets_with_dup(mut nums: Vec<i32>) -> Vec<Vec<i32>> {
let mut res = HashSet::new();
let mut path = vec![];
nums.sort();
Self::backtracking(&nums, &mut path, &mut res, 0);
res.into_iter().collect()
}
pub fn backtracking(
nums: &Vec<i32>,
path: &mut Vec<i32>,
res: &mut HashSet<Vec<i32>>,
start_index: usize,
) {
res.insert(path.clone());
for i in start_index..nums.len() {
path.push(nums[i]);
Self::backtracking(nums, path, res, i + 1);
path.pop();
}
}
}
int* path;
int pathTop;
int** ans;
int ansTop;
//负责存放二维数组中每个数组的长度
int* lengths;
//快排cmp函数
int cmp(const void* a, const void* b) {
return *((int*)a) - *((int*)b);
}
//复制函数,将当前path中的元素复制到ans中。同时记录path长度
void copy() {
int* tempPath = (int*)malloc(sizeof(int) * pathTop);
int i;
for(i = 0; i < pathTop; i++) {
tempPath[i] = path[i];
}
ans = (int**)realloc(ans, sizeof(int*) * (ansTop + 1));
lengths[ansTop] = pathTop;
ans[ansTop++] = tempPath;
}
void backTracking(int* nums, int numsSize, int startIndex, int* used) {
//首先将当前path复制
copy();
//若startIndex大于数组最后一位元素的位置,返回
if(startIndex >= numsSize)
return ;
int i;
for(i = startIndex; i < numsSize; i++) {
//对同一树层使用过的元素进行跳过
if(i > 0 && nums[i] == nums[i-1] && used[i-1] == false)
continue;
path[pathTop++] = nums[i];
used[i] = true;
backTracking(nums, numsSize, i + 1, used);
used[i] = false;
pathTop--;
}
}
int** subsetsWithDup(int* nums, int numsSize, int* returnSize, int** returnColumnSizes){
//声明辅助变量
path = (int*)malloc(sizeof(int) * numsSize);
ans = (int**)malloc(0);
lengths = (int*)malloc(sizeof(int) * 1500);
int* used = (int*)malloc(sizeof(int) * numsSize);
pathTop = ansTop = 0;
//排序后查重才能生效
qsort(nums, numsSize, sizeof(int), cmp);
backTracking(nums, numsSize, 0, used);
//设置一维数组和二维数组的返回大小
*returnSize = ansTop;
*returnColumnSizes = (int*)malloc(sizeof(int) * ansTop);
int i;
for(i = 0; i < ansTop; i++) {
(*returnColumnSizes)[i] = lengths[i];
}
return ans;
}
func subsetsWithDup(_ nums: [Int]) -> [[Int]] {
let nums = nums.sorted()
var result = [[Int]]()
var path = [Int]()
func backtracking(startIndex: Int) {
// 直接收集结果
result.append(path)
let end = nums.count
guard startIndex < end else { return } // 终止条件
for i in startIndex ..< end {
if i > startIndex, nums[i] == nums[i - 1] { continue } // 跳过重复元素
path.append(nums[i]) // 处理:收集元素
backtracking(startIndex: i + 1) // 元素不重复访问
path.removeLast() // 回溯
}
}
backtracking(startIndex: 0)
return result
}
不使用used数组:
object Solution {
import scala.collection.mutable
def subsetsWithDup(nums: Array[Int]): List[List[Int]] = {
var result = mutable.ListBuffer[List[Int]]()
var path = mutable.ListBuffer[Int]()
var num = nums.sorted // 排序
def backtracking(startIndex: Int): Unit = {
result.append(path.toList)
if (startIndex >= num.size){
return
}
for (i <- startIndex until num.size) {
// 同一树层重复的元素不进入回溯
if (!(i > startIndex && num(i) == num(i - 1))) {
path.append(num(i))
backtracking(i + 1)
path.remove(path.size - 1)
}
}
}
backtracking(0)
result.toList
}
}
使用Set去重:
object Solution {
import scala.collection.mutable
def subsetsWithDup(nums: Array[Int]): List[List[Int]] = {
var result = mutable.Set[List[Int]]()
var num = nums.sorted
def backtracking(path: mutable.ListBuffer[Int], startIndex: Int): Unit = {
if (startIndex == num.length) {
result.add(path.toList)
return
}
path.append(num(startIndex))
backtracking(path, startIndex + 1) // 选择
path.remove(path.size - 1)
backtracking(path, startIndex + 1) // 不选择
}
backtracking(mutable.ListBuffer[Int](), 0)
result.toList
}
}
public class Solution
{
public IList<IList<int>> res = new List<IList<int>>();
public IList<int> path = new List<int>();
public IList<IList<int>> SubsetsWithDup(int[] nums)
{
Array.Sort(nums);
BackTracking(nums, 0);
return res;
}
public void BackTracking(int[] nums, int start)
{
res.Add(new List<int>(path));
for (int i = start; i < nums.Length; i++)
{
if (i > start && nums[i] == nums[i - 1]) continue;
path.Add(nums[i]);
BackTracking(nums, i + 1);
path.RemoveAt(path.Count - 1);
}
}
}