Leetcode - Permutations I,II
Leetcode - 046 Permutations
全配列問題は遡及の典型的な例題である:1.可行解の構成形態は、所与の配列における全ての数の組み合わせであるため、大きさ的に可行解判定条件2とすることができる.選択可能な残りのセットのうち1つを選択するたびにmask配列を作成する
Leetcode - 047. Permutations II
diff:val 1=val 2の場合を考慮する必要があり、sortが同じ要素をクラスタリングし、前述のLeetcode - 040. Combination Sum IIを参照して重量を除去する方法が必要です.
全配列問題は遡及の典型的な例題である:1.可行解の構成形態は、所与の配列における全ての数の組み合わせであるため、大きさ的に可行解判定条件2とすることができる.選択可能な残りのセットのうち1つを選択するたびにmask配列を作成する
class Solution {
public:
void dfs(vector> &vct, vector &cur, vector& nums,vector & used)
{
if (cur.size() == nums.size())
{
vct.push_back(cur);
return;
}
for (int i = 0; i < nums.size(); ++i)
{
if (used[i] == 0)
{
cur.push_back(nums[i]);
used[i] = 1;
dfs(vct, cur, nums, used);
used[i] = 0;
cur.pop_back();
}
}
}
vector> permute(vector& nums) {
vector> vct;
int n = nums.size();
if (n <= 0)
return vct;
vector cur;
vector used(n, 0);
dfs(vct, cur, nums, used);
return vct;
}
}; Leetcode - 047. Permutations II
diff:val 1=val 2の場合を考慮する必要があり、sortが同じ要素をクラスタリングし、前述のLeetcode - 040. Combination Sum IIを参照して重量を除去する方法が必要です.
class Solution {
public:
void dfs(vector> &vct, vector &cur, vector& nums, vector & used)
{
if (cur.size() == nums.size())
{
vct.push_back(cur);
return;
}
for (int i = 0; i < nums.size(); ++i)
{
if (used[i] == 0)
{
int pre_index = i - 1;
bool repeated = false;
while (pre_index >= 0 && nums[pre_index] == nums[i])
{
if (used[pre_index] == 0)
{
repeated = true;
break;
}
--pre_index;
}
if (repeated)
continue;
cur.push_back(nums[i]);
used[i] = 1;
dfs(vct, cur, nums, used);
used[i] = 0;
cur.pop_back();
}
}
}
vector> permuteUnique(vector& nums) {
vector> vct;
vector cur;
int n = nums.size();
if (n <= 0)
return vct;
vector used(n, 0);
dfs(vct, cur, nums, used);
return vct;
}
};