两种方法:
一. 回溯:
C++:
class Solution { public: vector<vector<int>>result; vector<int>path; void backtracing(vector<int>S,int len,int index){ result.push_back(path); for(int i=index;i<len;++i){ path.push_back(s[i]); backtracing(s,len,index+1); path.pop_back(); } vector<vector<int> > subsets(vector<int> &S) { result.clear(); path.clear(); sort(S.begin(),S.end()); backtracing(S,S.size(),0); return result; } };
JAVA:
import java.util.*; public class Solution { ArrayList<arraylist<integer>>result=new ArrayList<>(); ArrayList<integer>path=new ArrayList<integer>(); void backtracing(int[] S,int len,int index){ result.add(new ArrayList<>(path));//不能跟C++一样直接result.add(path)....... for(int i=index;i<len;++i){ path.add(s[i]); backtracing(s,len,i+1); path.remove(path.size()-1); } public arraylist<arraylist<integer>> subsets(int[] S) { Arrays.sort(S); backtracing(S,S.length,0); return result; } }
python3:
# # # @param A int整型一维数组 # @return int整型二维数组 # class Solution: def backtracing(self,A,length:int,index:int,ans1,path1): ans1.append(path1.copy()) for i in range(index,length): path1.append(A[i]) self.backtracing(A, length,i+1,ans1,path1) path1.pop() def subsets(self , A ): # write code here length=len(A) A.sort() ans=[] path=[] self.backtracing(A, length, 0,ans,path) return ans
二.迭代:
C++:
class Solution { public: vector<vector<int> > subsets(vector<int> &S) { vector<vector<int>>ans; int n=S.size(); //注意要先push一个子集 ans.push_back({}); for(int i=0;i<n;++i){ int size=ans.size(); for(int j=0;j<size;++j){ vector<int>path(ans[j]); path.push_back(S[i]); ans.push_back(path); } } return ans; } };
JAVA:
import java.util.*; public class Solution { public ArrayList<ArrayList<Integer>> subsets(int[] S) { int n=S.length; ArrayList<ArrayList<Integer>>ans=new ArrayList<>(); ans.add(new ArrayList<Integer>()); for(int i=0;i<n;++i){ int size=ans.size(); for(int j=0;j<size;++j){ ArrayList<Integer>path=new ArrayList<Integer>(); path.addAll(ans.get(j)); path.add(S[i]); ans.add(path); } } return ans; } }
python:
# # # @param A int整型一维数组 # @return int整型二维数组 # class Solution: def subsets(self , A ): # write code here res=[[]] for item in A: res+=[i+[item] for i in res] return res