C++ leetcode之排列与组合专题
2023-09-14 09:01:28 时间
目录
排列与组合
排列组合是组合学最基本的概念。所谓排列,就是指从给定个数的元素中取出指定个数的元素进行排序。组合则是指从给定个数的元素中仅仅取出指定个数的元素,不考虑排序。
1. 全排列
给定一个 没有重复 数字的序列,返回其所有可能的全排列。
示例:
输入: [1,2,3] 输出:[[1,2,3], [1,3,2], [2,1,3], [2,3,1], [3,1,2], [3,2,1]]
方法一
#include <bits/stdc++.h>
using namespace std;
class Solution
{
public:
vector<vector<int>> permute(vector<int> &nums)
{
vector<vector<int>> res;
vector<bool> used(nums.size());
dfs(nums, used, res);
return res;
}
private:
vector<int> stack;
void dfs(vector<int> &nums, vector<bool> &used, vector<vector<int>> &res)
{
if (stack.size() == nums.size())
{
res.push_back(stack);
}
else
{
for (int i = 0; i < nums.size(); i++)
{
if (!used[i])
{
used[i] = true;
stack.push_back(nums[i]);
dfs(nums, used, res);
stack.pop_back();
used[i] = false;
}
}
}
}
};
int main()
{
vector<int> nums = {1,2,3};
Solution s;
for (auto res : s.permute(nums)){
for (auto item : res)
cout << item << " ";
cout << endl;
}
cout << endl;
return 0;
}
方法二
#include <bits/stdc++.h>
using namespace std;
class Solution
{
public:
vector<vector<int>> result;
vector<vector<int>> permute(vector<int> &nums)
{
vector<int> temp(nums.size());
permutation(nums.size(), 0, nums, temp);
return result;
}
void permutation(int n, int index, vector<int> &nums, vector<int> &temp)
{
if (index == n)
{
result.push_back(temp);
return;
}
for (int i = 0; i < n; i++)
{
bool flag = true;
for (int j = 0; j <= index - 1; j++)
{
if (temp[j] == nums[i])
flag = false;
}
if (flag)
{
temp[index] = nums[i];
permutation(n, index + 1, nums, temp);
}
}
}
};
int main()
{
vector<int> nums = {1,2,3};
Solution s;
for (auto res : s.permute(nums)){
for (auto item : res)
cout << item << " ";
cout << endl;
}
cout << endl;
return 0;
}
方法三
#include <bits/stdc++.h>
using namespace std;
class Solution
{
public:
vector<vector<int>> permute(vector<int> &nums)
{
vector<vector<int>> res;
BT(res, nums, 0);
return res;
}
void BT(vector<vector<int>> &res, vector<int> &nums, int start)
{
if (start == nums.size())
{
res.push_back(nums);
return;
}
else
{
for (int i = start; i < nums.size(); i++)
{
swap(nums[i], nums[start]);
BT(res, nums, start + 1);
swap(nums[i], nums[start]);
}
}
}
};
int main()
{
vector<int> nums = {1,2,3};
Solution s;
for (auto res : s.permute(nums)){
for (auto item : res)
cout << item << " ";
cout << endl;
}
cout << endl;
return 0;
}
2. 全排列 II
给定一个可包含重复数字的序列 nums
,按任意顺序 返回所有不重复的全排列。
示例 1:
输入:nums = [1,1,2] 输出:[[1,1,2], [1,2,1], [2,1,1]]
示例 2:
输入:nums = [1,2,3] 输出:[[1,2,3],[1,3,2],[2,1,3],[2,3,1],[3,1,2],[3,2,1]]
提示:
1 <= nums.length <= 8
-10 <= nums[i] <= 10
方法一
#include <bits/stdc++.h>
using namespace std;
class Solution
{
public:
vector<vector<int>> permuteUnique(vector<int> &nums)
{
vector<vector<int>> res;
int n = nums.size();
vector<int> temp;
vector<bool> visited(n, false);
sort(nums.begin(), nums.end());
backtrackpermuteUnique(0, n, nums, temp, res, visited);
return res;
}
void backtrackpermuteUnique(int k, int n, vector<int> nums, vector<int> &temp, vector<vector<int>> &res, vector<bool> &visited)
{
if (k == n)
{
res.push_back(temp);
return;
}
for (int i = 0; i < n; i++)
{
if (!visited[i])
{
if (i > 0 && nums[i] == nums[i - 1] && visited[i - 1])
continue;
temp.push_back(nums[i]);
visited[i] = true;
backtrackpermuteUnique(k + 1, n, nums, temp, res, visited);
temp.pop_back();
visited[i] = false;
}
}
}
};
int main()
{
vector<int> nums = {1,1,2};
Solution s;
for (auto res : s.permuteUnique(nums)){
for (auto item : res)
cout << item << " ";
cout << endl;
}
cout << endl;
return 0;
}
方法二
#include <bits/stdc++.h>
using namespace std;
class Solution
{
public:
vector<vector<int>> permuteUnique(vector<int> &nums)
{
vector<vector<int>> res;
vector<bool> used(nums.size());
sort(nums.begin(), nums.end());
dfs(nums, used, res);
return res;
}
private:
vector<int> stack;
void dfs(vector<int> &nums, vector<bool> &used, vector<vector<int>> &res)
{
if (stack.size() == nums.size())
{
res.push_back(stack);
}
else
{
for (int i = 0; i < nums.size(); i++)
{
if (!used[i])
{
if (i > 0 && !used[i - 1] && nums[i - 1] == nums[i])
{
continue;
}
stack.push_back(nums[i]);
used[i] = true;
dfs(nums, used, res);
stack.pop_back();
used[i] = false;
}
}
}
}
};
int main()
{
vector<int> nums = {1,1,2};
Solution s;
for (auto res : s.permuteUnique(nums)){
for (auto item : res)
cout << item << " ";
cout << endl;
}
cout << endl;
return 0;
}
3. 组合总和
给定一个无重复元素的数组 candidates
和一个目标数 target
,找出 candidates
中所有可以使数字和为 target
的组合。
candidates
中的数字可以无限制重复被选取。
说明:
- 所有数字(包括
target
)都是正整数。 - 解集不能包含重复的组合。
示例 1:
输入:candidates = [2,3,6,7], target = 7, 输出:[[7],[2,2,3]]
示例 2:
输入:candidates = [2,3,5], target = 8, 输出:[[2,2,2,2],[2,3,3],[3,5]]
提示:
1 <= candidates.length <= 30
1 <= candidates[i] <= 200
candidate
中的每个元素都是独一无二的。1 <= target <= 500
方法一
#include <bits/stdc++.h>
using namespace std;
class Solution
{
public:
void compute(int start, int target, vector<int> &tmp, vector<int> &candidates, vector<vector<int>> &ans)
{
int n = candidates.size();
for (int i = start; i < n; i++)
{
if (target > 0)
{
tmp.push_back(candidates[i]);
compute(i, target - candidates[i], tmp, candidates, ans);
tmp.pop_back();
}
else if (target < 0)
return;
else
{
ans.push_back(tmp);
return;
}
}
}
vector<vector<int>> combinationSum(vector<int> &candidates, int target)
{
vector<vector<int>> ans;
vector<int> tmp;
int v;
sort(candidates.begin(), candidates.end());
compute(0, target, tmp, candidates, ans);
return ans;
}
};
int main()
{
vector<int> result, candidates = {2,3,6,7};
int target = 7;
Solution s;
for (auto candidate : s.combinationSum(candidates, target)){
for (auto item : candidate)
cout << item << " ";
cout << endl;
}
cout <<endl;
candidates = {2,3,5};
target = 8;
for (auto candidate : s.combinationSum(candidates, target)){
for (auto item : candidate)
cout << item << " ";
cout << endl;
}
return 0;
}
方法二
#include <bits/stdc++.h>
using namespace std;
class Solution
{
public:
vector<vector<int>> combinationSum(vector<int> &candidates, int target)
{
vector<vector<int>> res;
dfs(candidates, 0, target, res);
return res;
}
private:
vector<int> stack;
void dfs(vector<int> &candidates, int start, int target, vector<vector<int>> &res)
{
if (target < 0)
{
return;
}
else if (target == 0)
{
res.push_back(stack);
}
else
{
for (int i = start; i < candidates.size(); i++)
{
stack.push_back(candidates[i]);
dfs(candidates, i, target - candidates[i], res);
stack.pop_back();
}
}
}
};
int main()
{
vector<int> result, candidates = {2,3,6,7};
int target = 7;
Solution s;
for (auto candidate : s.combinationSum(candidates, target)){
for (auto item : candidate)
cout << item << " ";
cout << endl;
}
cout <<endl;
candidates = {2,3,5};
target = 8;
for (auto candidate : s.combinationSum(candidates, target)){
for (auto item : candidate)
cout << item << " ";
cout << endl;
}
return 0;
}
方法三
#include <bits/stdc++.h>
using namespace std;
class Solution
{
private:
vector<vector<int>> res;
vector<int> ans;
public:
vector<vector<int>> combinationSum(vector<int> &candidates, int target)
{
sort(candidates.begin(), candidates.end());
int left = 0, right = 0;
for (; right < candidates.size() && candidates[right] <= target; right++)
;
backtrack(candidates, left, right == candidates.size() ? right - 1 : right, target);
return res;
}
private:
void backtrack(vector<int> &candidates, int left, int right, int target)
{
if (target < 0)
return;
if (!target)
{
res.push_back(ans);
return;
}
for (int i = left; i <= right && candidates[i] <= target; i++)
{
ans.push_back(candidates[i]);
backtrack(candidates, i, right, target - candidates[i]);
ans.pop_back();
}
}
};
int main()
{
vector<int> result, candidates = {2,3,6,7};
int target = 7;
Solution s;
for (auto candidate : s.combinationSum(candidates, target)){
for (auto item : candidate)
cout << item << " ";
cout << endl;
}
cout <<endl;
candidates = {2,3,5};
target = 8;
Solution s2;
for (auto candidate : s2.combinationSum(candidates, target)){
for (auto item : candidate)
cout << item << " ";
cout << endl;
}
return 0;
}
4. 组合总和 II
给定一个数组 candidates
和一个目标数 target
,找出 candidates
中所有可以使数字和为 target
的组合。
candidates
中的每个数字在每个组合中只能使用一次。
说明:
- 所有数字(包括目标数)都是正整数。
- 解集不能包含重复的组合。
示例 1:
输入: candidates = [10,1,2,7,6,1,5], target = 8, 所求解集为:[[1, 7],[1, 2, 5],[2, 6],[1, 1, 6]]
示例 2:
输入: candidates = [2,5,2,1,2], target = 5, 所求解集为:[[1,2,2],[5]]
方法一
#include <bits/stdc++.h>
using namespace std;
class Solution
{
public:
vector<vector<int>> combinationSum2(vector<int> &candidates, int target)
{
vector<vector<int>> res;
sort(candidates.begin(), candidates.end());
dfs(candidates, 0, target, res);
return res;
}
private:
vector<int> stack;
void dfs(vector<int> &candidates, int start, int target, vector<vector<int>> &res)
{
if (target < 0)
{
return;
}
else if (target == 0)
{
res.push_back(stack);
}
else
{
int last = INT_MIN;
for (int i = start; i < candidates.size(); i++)
{
if (last != candidates[i])
{
stack.push_back(candidates[i]);
dfs(candidates, i + 1, target - candidates[i], res);
stack.pop_back();
}
last = candidates[i];
}
}
}
};
int main()
{
vector<int> candidates = {10,1,2,7,6,1,5};
int target = 8;
Solution s;
for (auto candidate : s.combinationSum2(candidates, target)){
for (auto item : candidate)
cout << item << " ";
cout << endl;
}
cout <<endl;
candidates = {2,5,2,1,2};
target = 5;
for (auto candidate : s.combinationSum2(candidates, target)){
for (auto item : candidate)
cout << item << " ";
cout << endl;
}
return 0;
}
方法二
#include <bits/stdc++.h>
using namespace std;
class Solution
{
public:
void dfs(vector<vector<int>> &ans, vector<int> &candidates, vector<int> &tmp, int target, int start)
{
if (target == 0)
{
ans.push_back(tmp);
return;
}
else if (target < 0)
{
return;
}
else
{
for (int i = start; i < candidates.size(); i++)
{
tmp.push_back(candidates[i]);
dfs(ans, candidates, tmp, target - candidates[i], i + 1);
tmp.pop_back();
while (i + 1 < candidates.size() && candidates[i] == candidates[i + 1])
i++;
}
}
}
vector<vector<int>> combinationSum2(vector<int> &candidates, int target)
{
vector<vector<int>> ans;
vector<int> tmp;
if (candidates.empty())
return ans;
sort(candidates.begin(), candidates.end());
dfs(ans, candidates, tmp, target, 0);
return ans;
}
};
int main()
{
vector<int> candidates = {10,1,2,7,6,1,5};
int target = 8;
Solution s;
for (auto candidate : s.combinationSum2(candidates, target)){
for (auto item : candidate)
cout << item << " ";
cout << endl;
}
cout <<endl;
candidates = {2,5,2,1,2};
target = 5;
for (auto candidate : s.combinationSum2(candidates, target)){
for (auto item : candidate)
cout << item << " ";
cout << endl;
}
return 0;
}
方法三
#include <bits/stdc++.h>
using namespace std;
class Solution
{
public:
vector<vector<int>> combinationSum2(vector<int> &candidates, int target)
{
vector<vector<int>> res;
vector<int> temp;
backtrace(candidates, temp, 0, target);
res.assign(m_set.begin(), m_set.end());
return res;
}
void backtrace(vector<int> &candidates,
vector<int> &temp,
int index,
int target)
{
if (target == 0)
{
sort(temp.begin(), temp.end());
/* 去重 */
m_set.insert(temp);
return;
}
/* 设定边界*/
if (index == candidates.size())
{
return;
}
if (target >= candidates[index])
{
vector<int> tmp(temp);
tmp.push_back(candidates[index]);
backtrace(candidates, tmp, index + 1, target - candidates[index]);
}
backtrace(candidates, temp, index + 1, target);
}
private:
set<vector<int>> m_set;
};
int main()
{
vector<int> candidates = {10,1,2,7,6,1,5};
int target = 8;
Solution s;
for (auto candidate : s.combinationSum2(candidates, target)){
for (auto item : candidate)
cout << item << " ";
cout << endl;
}
cout <<endl;
candidates = {2,5,2,1,2};
target = 5;
Solution s2;
for (auto candidate : s2.combinationSum2(candidates, target)){
for (auto item : candidate)
cout << item << " ";
cout << endl;
}
return 0;
}
相关文章
- C++string类作为形参传值,实参与形参的变化
- EasyC++34,指针与引用的异同
- 深入理解C++11_c++ string char
- c++ auto类型_auto C++
- 【c++】【基础】【primer_plus】【第七章】函数指针
- 2022蓝桥杯(c/c++ B组)-刷题统计
- C++类和对象(上)
- C++数学与算法系列之初等数论
- 软件开发入门教程网之C++ 标准库
- c++版本cef详细使用
- C/C++生态工具链——内存泄露检测工具Valgrind
- C++ duration(STL duration)模板用法详解
- MySQL56和C开发开启新时代数据管理之旅(c++ mysql5.6)
- C++中函数的默认参数详细解析