Skip to content

Latest commit

 

History

History
666 lines (571 loc) · 18.3 KB

0090.子集II.md

File metadata and controls

666 lines (571 loc) · 18.3 KB
Raw

参与本项目，贡献其他语言版本的代码，拥抱开源，让更多学习算法的小伙伴们收益！

90.子集II

力扣题目链接

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

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

示例:

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

算法公开课

《代码随想录》算法视频公开课：回溯算法解决子集问题，如何去重？| LeetCode：90.子集II，相信结合视频再看本篇题解，更有助于大家对本题的理解。

思路

做本题之前一定要先做78.子集。

这道题目和78.子集区别就是集合里有重复元素了，而且求取的子集要去重。

那么关于回溯算法中的去重问题，在40.组合总和II中已经详细讲解过了，和本题是一个套路。

剧透一下，后期要讲解的排列问题里去重也是这个套路，所以理解“树层去重”和“树枝去重”非常重要。

用示例中的[1, 2, 2] 来举例，如图所示： （注意去重需要先对集合排序）

90.子集II

从图中可以看出，同一树层上重复取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。

其他语言版本

Java

使用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();
    }
  }

}

Python3

回溯 利用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()

Go

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]
    }
}

Javascript

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
};

TypeScript

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
};

Rust

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();
        }
    }
}

C

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;
}

Swift

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
}

Scala

不使用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
  }
}

C#

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);
        }
    }
}