給你一個整數(shù)數(shù)組 nums ，其中可能包含重復(fù)元素，請你返回該數(shù)組所有可能的子集（冪集）。

解集 不能 包含重復(fù)的子集。返回的解集中，子集可以按 任意順序 排列。

示例 1：

輸入：nums = [1,2,2]
輸出：[[],[1],[1,2],[1,2,2],[2],[2,2]]

解題思路

通過排序，將相同的元素排在一起，在進行回溯的時候，一個遞歸的節(jié)點內(nèi)只允許重復(fù)的元素出現(xiàn)一次

代碼

class Solution {List<List<Integer>> lists=new ArrayList<>();public void bc(int[] arr,int cur,LinkedList<Integer> list) {lists.add(new LinkedList<>(list));for(int i=cur;i<arr.length;i++){if(i>cur&&arr[i]==arr[i-1]) continue;list.addLast(arr[i]);bc(arr, i+1, list);list.removeLast();}}public List<List<Integer>> subsetsWithDup(int[] nums) {Arrays.sort(nums);bc(nums,0,new LinkedList<>());return lists;} }

總結(jié)

以上是生活随笔為你收集整理的leetcode 90. 子集 II（回溯算法）的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯，歡迎將生活随笔推薦給好友。