問題描述

給定一組不含重複元素的整數數組 nums，返回該數組所有可能的子集（幂集）。

說明：解集不能包含重複的子集。

示例:

輸入: nums = [1,2,3]

輸出:

[

[3],

[1],

[2],

[1,2,3],

[1,3],

[2,3],

[1,2],

[]

]

回溯解決解決

在前面一道題450，什麼叫回溯算法，一看就會，一寫就廢中提到過子集的問題，這裡再來看一下，回溯的模闆如下，就是先選擇，最後再撤銷

private void backtrack("原始參數") { //終止條件(遞歸必須要有終止條件) if ("終止條件") { //一些邏輯操作（可有可無，視情況而定） return; } for (int i = "for循環開始的參數"; i < "for循環結束的參數"; i ) { //一些邏輯操作（可有可無，視情況而定） //做出選擇 //遞歸 backtrack("新的參數"); //一些邏輯操作（可有可無，視情況而定） //撤銷選擇 } }

這道題也一樣，可以把它想象成為一顆n叉樹，通過DFS遍曆這棵n叉樹，他所走過的所有路徑都是子集的一部分，看下代碼

public List<List<Integer>> subsets(int[] nums) { List<List<Integer>> list = new ArrayList<>(); backtrack(list, new ArrayList<>(), nums, 0); return list; } private void backtrack(List<List<Integer>> list, List<Integer> tempList, int[] nums, int start) { //走過的所有路徑都是子集的一部分，所以都要加入到集合中 list.add(new ArrayList<>(tempList)); for (int i = start; i < nums.length; i ) { //做出選擇 tempList.add(nums[i]); //遞歸 backtrack(list, tempList, nums, i 1); //撤銷選擇 tempList.remove(tempList.size() - 1); } }

因為在第450題剛講過這道題，所以基本上沒什麼難度，其實這道題還可以使用位運算解決，來看下

位運算解決

數組中的每一個數字都有選和不選兩種狀态，我們可以用0和1表示，0表示不選，1表示選擇。如果數組的長度是n，那麼子集的數量就是2^n。比如數組長度是3，就有8種可能，分别是

[0，0，0]

[0，0，1]

[0，1，0]

[0，1，1]

[1，0，0]

[1，0，1]

[1，1，0]

[1，1，1]

這裡參照示例畫個圖來看下

public static List<List<Integer>> subsets(int[] nums) { //子集的長度是2的nums.length次方，這裡通過移位計算 int length = 1 << nums.length; List<List<Integer>> res = new ArrayList<>(length); //遍曆從0到length中間的所有數字，根據數字中1的位置來找子集 for (int i = 0; i < length; i ) { List<Integer> list = new ArrayList<>(); for (int j = 0; j < nums.length; j ) { //如果數字i的某一個位置是1，就把數組中對 //應的數字添加到集合 if (((i >> j) & 1) == 1) list.add(nums[j]); } res.add(list); } return res; }

非遞歸解決

這題還有其他解題思路，比如先加入一個空集讓他成為新的子集，然後每遍曆一個元素就在原來的子集的後面追加這個值。還以示例來分析下

public List<List<Integer>> subsets(int[] nums) { List<List<Integer>> res = new ArrayList<>(1 << nums.length); //先添加一個空的集合 res.add(new ArrayList<>()); for (int num : nums) { //每遍曆一個元素就在之前子集中的每個集合追加這個元素，讓他變成新的子集 for (int i = 0, j = res.size(); i < j; i ) { //遍曆之前的子集，重新封裝成一個新的子集 List<Integer> list = new ArrayList<>(res.get(i)); //然後在新的子集後面追加這個元素 list.add(num); //把這個新的子集添加到集合中 res.add(list); } } return res; }

如果非要把它改為遞歸的也是可以的，僅僅提供了一種思路，有興趣的也可以看下

public List<List<Integer>> subsets(int[] nums) { List<List<Integer>> res = new ArrayList<>(1 << nums.length); res.add(new ArrayList<>()); recursion(nums, 0, res); return res; } public static void recursion(int[] nums, int index, List<List<Integer>> res) { //數組中的元素都訪問完了，直接return if (index >= nums.length) return; int size = res.size(); for (int j = 0; j < size; j ) { List<Integer> list = new ArrayList<>(res.get(j)); //然後在新的子集後面追加一個值 list.add(nums[index]); res.add(list); } //遞歸下一個元素 recursion(nums, index 1, res); }

其他解決方式

在426，什麼是遞歸，通過這篇文章，讓你徹底搞懂遞歸中最後講到分支污染的時候提到過這樣一個問題：生成一個2n長的數組，數組的值從0到(2n)-1。我們可以把它想象成為一顆二叉樹，每個節點的子樹都是一個可選一個不可選

所以我們也可以參照這種方式來寫，代碼如下

public List<List<Integer>> subsets(int[] nums) { List<List<Integer>> res = new ArrayList<>(); helper(res, nums, new ArrayList<>(), 0); return res; } private void helper(List<List<Integer>> res, int[] nums, List<Integer> list, int index) { //終止條件判斷 if (index == nums.length) { res.add(new ArrayList<>(list)); return; } //每一個節點都有兩個分支，一個選一個不選 //走不選這個分支 helper(res, nums, list, index 1); //走選擇這個分支 list.add(nums[index]); helper(res, nums, list, index 1); //撤銷選擇 list.remove(list.size() - 1); }

總結

這題難度不大，但解法比較多，上面介紹的每一種基本上都是一種新的解題思路，如果能全部掌握将會有很大收獲。

,

更多精彩资讯请关注tft每日頭條，我们将持续为您更新最新资讯!

查看全部