冪集問題-有解無憂

問題描述：

給定一組不含重復元素的整數陣列 nums，回傳該陣列所有可能的子集（冪集），示例：輸入: nums = [1,2,3] 輸出: [
[3], [1], [2], [1,2,3], [1,3], [2,3], [1,2], [] ]
說明：解集不能包含重復的子集，

觀察全排列/組合/子集問題，它們比較相似，且可以使用一些通用策略解決，

首先，它們的解空間非常大：

全排列：N!，
組合：N!，
子集：2^N^，每個元素都可能存在或不存在，

在它們的指數級解法中，要確保生成的結果完整且 無冗余

思路：這是一個典型的應用回溯法的題目，簡單來說就是窮盡所有可能性，演算法模板如下：

1 result = []
2 func backtrack(選擇串列,路徑):
3 　　if 滿足結束條件:
4 　　result.add(路徑)
5 　　return
6 for 選擇 in 選擇串列:
7 　　做選擇
8 　　backtrack(選擇串列,路徑)
9 　　撤銷選擇

通過不停的選擇，撤銷選擇，來窮盡所有可能性，最后將滿足條件的結果回傳

復雜度分析

時間復雜度：O(N×2^N)，生成所有子集，并復制到輸出集合中，

空間復雜度：O(N×2^N)，存盤所有子集，共 nn 個元素，每個元素都有可能存在或者不存在，

代碼：

 1 class Solution {
 2     public static List<List<Integer>> subsets(int[] nums) {
 3         arr = nums;
 4         len = nums.length;
 5         G = new boolean[len];
 6         dfs(0);
 7         return lists;
 8     }
 9     public static void dfs(int i) {
10         //遍歷完整個陣列長度后，把被選中的添加到結果集中去（lists）
11         if(i == len) {
12             List<Integer> ls = new ArrayList<Integer>();
13             for (int k = 0; k < len; k++) {
14                 if(G[k]) {
15                     ls.add(arr[k]);
16                 }
17             }
18             lists.add(ls);
19             return;
20         }
21         //不選第i個元素
22         G[i] = false;
23         dfs(i + 1);
24         //選第i個元素
25         G[i] = true;
26         dfs(i + 1);
27     }
28     public static int[] arr;//陣列
29     public static boolean[] G;//標記 true代表選中，false代表沒被選中
30     public static int len;//陣列長度
31     public static List<List<Integer>> lists = new ArrayList<>();//冪集
32     
33     public static void main(String[] args) {
34 
35         System.out.println(subsets(new int[] {1, 2, 3}));
36     }
37 }

轉載請註明出處，本文鏈接：https://www.uj5u.com/qita/658.html

標籤：其他

上一篇：二叉樹的遍歷遞回非遞回

下一篇：1022. Sum of Root To Leaf Binary Numbers (E)