首页 > 代码库 > LeetCode: Subsets [078]
LeetCode: Subsets [078]
【题目】
Given a set of distinct integers, S, return all possible subsets.
Note:
- Elements in a subset must be in non-descending order.
- The solution set must not contain duplicate subsets.
For example,
If S = [1,2,3]
, a solution is:
[ [3], [1], [2], [1,2,3], [1,3], [2,3], [1,2], [] ]
【题意】
给定一个无重复的数字集合,返回所有该集合的自己,要求1. 不能出现重复的子集
2. 子集中的值递增排列
【思路】
本题是combinations的拓展,假设给定的数字集合的大小为n, 则我们需要依次找出长度为0,1,2,...n的组合为了使组合自然有序,我们需要先对原始集合进行排序。
【代码】
class Solution { public: void dfs(vector<vector<int> >&result, vector<int>combination, vector<int>&candidates, int kth, int k, int index2add){ // 当前正在确定组合中的第kth个数,将把候选集candidates中index2add索引位的值作为第kth个数加到组合中 combination.push_back(candidates[index2add-1]); if(kth==k){ result.push_back(combination); } else{ for(int i=index2add+1; i+(k-kth-1)<=candidates.size(); i++){ dfs(result, combination, candidates, kth+1, k, i); } } } vector<vector<int> > getKsubset(vector<int> &S, int k){ // 获得k元子集合 vector<vector<int> >result; vector<int> combination; for(int i=1; i+(k-1)<=S.size(); i++){ dfs(result, combination, S, 1, k, i); } return result; } vector<vector<int> > subsets(vector<int> &S) { vector<vector<int> >result; //一定有一个空集 vector<int> nonVector; result.push_back(nonVector); int size=S.size(); if(size==0)return result; //排序 sort(S.begin(), S.end()); for(int k=1; k<=size; k++){ //依次找k元组合 vector<vector<int> >ksubsets = getKsubset(S, k); result.insert(result.end(), ksubsets.begin(), ksubsets.end()); } return result; } };
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。