78/90 Subsets (I/II)
Total Accepted: 87879
Total Submissions: 285264
Difficulty: Medium
Given a set of distinct integers, nums, 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 nums =
Subscribe to see which companies asked this question
Hide Tags
Array Backtracking Bit Manipulation
Hide Similar Problems
(M) Generalized Abbreviation
分析:
本題と前のブログ77.Combinations
のテーマの意味は基本的に同じで、主な違いはまた異なるlenのサブ配列を遡及する必要があるので、遡及法は最終的に答えを確定する方法が違います.
(本題はlenを遡及時に答えを確定する根拠とする)
本題連動:
216. Combination Sum III
77. Combinations
39./40 Combination Sum(I/II)
他人のアルゴリズムを学ぶ1:ビット操作
原文の住所http://blog.csdn.net/u012501459/article/details/46777141
配列[1,2,3]については、この数字が選択されているか否かを1つの下付き文字0と1で表すことができ、0は選択されていないことを表し、1は選択を表し、3つのグループごとに3つの0と1の組み合わせは1つの選択を表し、3ビットには8つの選択があり、それぞれ:000対応[]001対応[0100対応[2]011対応[2,3]100...101,110,111である.では、0から1<
他人のアルゴリズムを学ぶ2:
Total Accepted: 62569
Total Submissions: 208285
Difficulty: Medium
Given a collection of integers that might contain duplicates, nums, 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 nums =
Subscribe to see which companies asked this question
Hide Tags
Array Backtracking
分析:
上のコードより同じ組み合わせの不要な遡及条件を1つ多く追加すればいいのですが、コードの速度は0.89%を打ち負かしました.つまり、極めて遅い速度で、もう爱しないような気がします.
他人のアルゴリズムを学ぶ:
注:本博文はEbowTangオリジナルで、その後も本論文を更新する可能性があります.転載する場合は、必ずこの情報をコピーしてください!
原文住所:http://blog.csdn.net/ebowtang/article/details/50844984
原作者ブログ:http://blog.csdn.net/ebowtang
このブログLeetCodeの問題解索引:http://blog.csdn.net/ebowtang/article/details/50668895
Total Submissions: 285264
Difficulty: Medium
Given a set of distinct integers, nums, 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 nums =
[1,2,3]
, a solution is: [
[3],
[1],
[2],
[1,2,3],
[1,3],
[2,3],
[1,2],
[]
]
Subscribe to see which companies asked this question
Hide Tags
Array Backtracking Bit Manipulation
Hide Similar Problems
(M) Generalized Abbreviation
分析:
本題と前のブログ
のテーマの意味は基本的に同じで、主な違いはまた異なるlenのサブ配列を遡及する必要があるので、遡及法は最終的に答えを確定する方法が違います.
(本題はlenを遡及時に答えを確定する根拠とする)
本題連動:
class Solution {
public:
void dfs(vector<int>& nums, vector<int> &subres, int start, int len)// ,
{
if (subres.size() == len)// ,
{
result.push_back(subres);
return;//
}
for (int i = start; i < nsize; i++)
{
subres.push_back(nums[i]);
dfs(nums, subres, i + 1, len);
subres.pop_back(); // ,
}
}
vector<vector<int>> subsets(vector<int>& nums) {
nsize=nums.size();
if ( nsize == 0)
return result;
sort(nums.begin(),nums.end()); // ,
vector<int> subres;
for(int len=0; len<=nums.size() ;len++)// ,
dfs(nums, subres, 0, len);
return result;
}
private:
vector<vector<int > > result;
int nsize;
};
他人のアルゴリズムを学ぶ1:ビット操作
原文の住所http://blog.csdn.net/u012501459/article/details/46777141
配列[1,2,3]については、この数字が選択されているか否かを1つの下付き文字0と1で表すことができ、0は選択されていないことを表し、1は選択を表し、3つのグループごとに3つの0と1の組み合わせは1つの選択を表し、3ビットには8つの選択があり、それぞれ:000対応[]001対応[0100対応[2]011対応[2,3]100...101,110,111である.では、0から1<
class Solution {
public:
vector<vector<int>> subsets(vector<int>& nums) {
int length=nums.size();
sort(nums.begin(),nums.end());
vector<vector<int> > result;
for(int i=0;i<1<<length;i++)
{
vector<int> tmp;
// i 1
for(int j=0;j<length;j++)
{
// i j 1
if(i&1<<j)
tmp.push_back(nums[j]);
}
result.push_back(tmp);
}
return result;
}
};
他人のアルゴリズムを学ぶ2:
class Solution {
public:
void dfs(vector<int> &s, int index, vector<int> &subset, vector<vector<int>> &res)
{
res.push_back(subset);
for(int i = index; i< s.size(); i++)
{
subset.push_back(s[i]);
dfs(s,i+1,subset,res);
subset.pop_back();
}
}
vector<vector<int>> subsets(vector<int>& nums) {
vector<vector<int>> result;
sort(nums.begin(),nums.end());
vector<int> subset;
dfs(nums,0,subset,result);
return result;
}
};
Total Accepted: 62569
Total Submissions: 208285
Difficulty: Medium
Given a collection of integers that might contain duplicates, nums, 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 nums =
[1,2,2]
, a solution is: [
[2],
[1],
[1,2,2],
[2,2],
[1,2],
[]
]
Subscribe to see which companies asked this question
Hide Tags
Array Backtracking
分析:
上のコードより同じ組み合わせの不要な遡及条件を1つ多く追加すればいいのですが、コードの速度は0.89%を打ち負かしました.つまり、極めて遅い速度で、もう爱しないような気がします.
class Solution {
public:
void dfs(vector<int>& nums, vector<int> &subres, int start, int len)// ,
{
if (subres.size() == len)// ,
{
if(!isSameVec(subres)) // ,
result.push_back(subres);
return;//
}
for (int i = start; i < nsize; i++)
{
subres.push_back(nums[i]);
dfs(nums, subres, i + 1, len);
subres.pop_back(); // ,
}
}
bool isSameVec(vector<int> &sub)
{
for(int i=0;i<result.size();i++)
{
if(result[i]==sub)
return true;
}
return false;
}
vector<vector<int>> subsetsWithDup(vector<int>& nums) {
nsize=nums.size();
if ( nsize == 0)
return result;
sort(nums.begin(),nums.end()); // ,
vector<int> subres;
for(int len=0; len<=nums.size() ;len++)// ,
dfs(nums, subres, 0, len);
return result;
}
private:
vector<vector<int > > result;
int nsize;
};
他人のアルゴリズムを学ぶ:
class Solution {
public:
void dfs(vector<int> &s, int index, vector<int> &subset, vector<vector<int>> &res)
{
res.push_back(subset);
for(int i = index; i< s.size(); i++)
{
if(i!=index && s[i]==s[i-1])
continue;
subset.push_back(s[i]);
dfs(s,i+1,subset,res);
subset.pop_back();
}
}
vector<vector<int> > subsetsWithDup(vector<int> &S) {
// Note: The Solution object is instantiated only once.
vector<vector<int>> result;
sort(S.begin(),S.end());
vector<int> subset;
dfs(S,0,subset,result);
return result;
}
};
注:本博文はEbowTangオリジナルで、その後も本論文を更新する可能性があります.転載する場合は、必ずこの情報をコピーしてください!
原文住所:http://blog.csdn.net/ebowtang/article/details/50844984
原作者ブログ:http://blog.csdn.net/ebowtang
このブログLeetCodeの問題解索引:http://blog.csdn.net/ebowtang/article/details/50668895