給定一組不含重復(fù)元素的整數(shù)數(shù)組?nums，返回該數(shù)組所有可能的子集（冪集）。

說明：解集不能包含重復(fù)的子集。

示例:

輸入: nums = [1,2,3] 輸出: [[3],[1],[2],[1,2,3],[1,3],[2,3],[1,2],[] ]來源：力扣（LeetCode） 鏈接：https://leetcode-cn.com/problems/subsets

?

方法一: 暴力法(擴展發(fā)) 效率比較慢

?

class Solution {public List<List<Integer>> subsets(int[] nums) {List<List<Integer>> resultList = new ArrayList<List<Integer>>();resultList.add(new ArrayList());for(int num : nums){System.out.println(num);int size = resultList.size();for(int i=0; i<size; i++){ArrayList cur = new ArrayList(resultList.get(i));cur.add(num);resultList.add(cur);}}System.out.println(resultList);return resultList;} }

?

?

?

方法二:回溯法

import java.util.ArrayList; import java.util.List;public class SubSets {public static void main(String[] args) {int[] nums = { 1,2,3};List<List<Integer>> res = new ArrayList<List<Integer>>();for(int i=0; i<nums.length+1; i++){backtracking(nums, i/*表示第i層*/ ,0/*每一層都從下標(biāo)0開始遍歷*/,res,new ArrayList()/*保存每一層的結(jié)果*/);}System.out.println(res);}/*** len: 層數(shù)* startIndex: 從數(shù)組哪個位置開始* res:最終結(jié)果* cur:保存每一層的結(jié)果*/ private static void backtracking(int[] nums, int len, int startIndex, List<List<Integer>> res, List<Integer> cur){if(cur.size() == len){// 當(dāng)前層len 是否等于 當(dāng)前層的結(jié)果list的長度res.add(new ArrayList(cur));return;}for(int i=startIndex; i<nums.length; i++){cur.add(nums[i]);backtracking(nums,len,i+1,res,cur);cur.remove(cur.size()-1);}}}

?

方法三:深度優(yōu)先dfs算法

import java.util.ArrayList; import java.util.List;public class Subsets {public static void main(String[] args) {int[] nums = {1, 2, 3};ArrayList res = new ArrayList();dfs(nums, 0, res, new ArrayList());System.out.println(res);}private static void dfs(int[] nums, int startIndex, List<List<Integer>> res, List<Integer> cur){res.add(new ArrayList<>(cur));for(int i=startIndex; i<nums.length; i++){cur.add(nums[i]);dfs(nums,i+1,res,cur);cur.remove(cur.size()-1);}} }

?

?

?

總結(jié)

以上是生活随笔為你收集整理的LeetCode 78. 子集的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。

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