文章目录
- 一、46.全排列I
- 二、47.全排列II
- 三、完整代码
所有的LeetCode题解索引,可以看这篇文章——【算法和数据结构】LeetCode题解。
一、46.全排列I
思路分析:本题要求是全排列,意味着每次递归的时候startIndex都要从0开始,否则只会得到一个[1 2 3]的组合。从零开始还需要筛选掉重复的组合,引入一个used数组,使用过的元素赋值为1,跳过该循环。因为是全排列,终止条件就是单个组合中元素个数等于nums数组大小。
程序如下:
class Solution {
private:vector<vector<int>> result;vector<int> path;void backtracking(const vector<int>& nums, int startIndex, vector<bool>& used) {if (path.size() == nums.size()) { // 终止条件result.push_back(path);return;}for (int i = startIndex; i < nums.size(); i++) {if (used[i]) continue;path.push_back(nums[i]); // 处理节点 used[i] = true;backtracking(nums, 0, used); // 递归used[i] = false;path.pop_back(); // 回溯}}
public:vector<vector<int>> permute(vector<int>& nums) {vector<bool> used(nums.size(), 0);backtracking(nums, 0, used);return result;}
};
复杂度分析:
- 时间复杂度: O ( n ! ) O(n!) O(n!)。
- 空间复杂度: O ( n ) O(n) O(n)。
二、47.全排列II
思路分析:在上一题的基础之上本题中的nums元素可以是重复的,因此需要进一步去重,首先题目对全排列组合的顺序没有要求,可以对nums数组进行排序操作。i>0的条件是对nums[i-1]的限制,表示数组的索引不能小于0。nums[i]等于nums[i-1]时就是出现了重复元素,当重复元素首次在nums(排序后的)中出现时(例如[1 1 2]中的第一个1),组合不会有重复的,再次出现时(第二个1),会出现重复组合,此时的used[i-1] = 0。这道题used[i-1]=0或者used[i-1]=1都能够去重,但是used[i-1]=0的去重效率更高。
程序如下:
class Solution {
private:vector<vector<int>> result;vector<int> path;void backtracking(const vector<int>& nums, int startIndex, vector<bool>& used) {if (path.size() == nums.size()) { // 终止条件result.push_back(path);return;}for (int i = startIndex; i < nums.size(); i++) {if (i > 0 && nums[i] == nums[i-1] && used[i-1] == 0 || used[i]) continue;path.push_back(nums[i]); // 处理节点 used[i] = true;backtracking(nums, 0, used); // 递归used[i] = false;path.pop_back(); // 回溯}}
public:vector<vector<int>> permuteUnique(vector<int>& nums) {vector<bool> used(nums.size(), 0);sort(nums.begin(), nums.end());backtracking(nums, 0, used);return result;}
};
复杂度分析:
- 时间复杂度: O ( n ! ∗ n ) O(n!*n) O(n!∗n)。
- 空间复杂度: O ( n ) O(n) O(n)。
三、完整代码
// 46全排列I
# include <iostream>
# include <string>
# include <vector>
using namespace std;class Solution {
private:vector<vector<int>> result;vector<int> path;void backtracking(const vector<int>& nums, int startIndex, vector<bool>& used) {if (path.size() == nums.size()) { // 终止条件result.push_back(path);return;}for (int i = startIndex; i < nums.size(); i++) {if (used[i]) continue;path.push_back(nums[i]); // 处理节点 used[i] = true;backtracking(nums, 0, used); // 递归used[i] = false;path.pop_back(); // 回溯}}
public:vector<vector<int>> permute(vector<int>& nums) {vector<bool> used(nums.size(), 0);backtracking(nums, 0, used);return result;}
};int main() {Solution s1;vector<int> nums = { 1, 2, 3 };vector<vector<int>> result = s1.permute(nums);for (vector<vector<int>>::iterator it = result.begin(); it != result.end(); it++) {for (vector<int>::iterator jt = (*it).begin(); jt != (*it).end(); jt++) {cout << *jt << " ";}cout << endl;}system("pause");return 0;
}
// 47全排列II
# include <iostream>
# include <string>
# include <vector>
# include <algorithm>
using namespace std;class Solution {
private:vector<vector<int>> result;vector<int> path;void backtracking(const vector<int>& nums, int startIndex, vector<bool>& used) {if (path.size() == nums.size()) { // 终止条件result.push_back(path);return;}for (int i = startIndex; i < nums.size(); i++) {if (i > 0 && nums[i] == nums[i-1] && used[i-1] == 0 || used[i]) continue;path.push_back(nums[i]); // 处理节点 used[i] = true;backtracking(nums, 0, used); // 递归used[i] = false;path.pop_back(); // 回溯}}
public:vector<vector<int>> permuteUnique(vector<int>& nums) {vector<bool> used(nums.size(), 0);sort(nums.begin(), nums.end());backtracking(nums, 0, used);return result;}
};int main() {Solution s1;vector<int> nums = { 1, 1, 2 };vector<vector<int>> result = s1.permuteUnique(nums);for (vector<vector<int>>::iterator it = result.begin(); it != result.end(); it++) {for (vector<int>::iterator jt = (*it).begin(); jt != (*it).end(); jt++) {cout << *jt << " ";}cout << endl;}system("pause");return 0;
}
end