46. Permutations, 47. Permutations II

本文主要是介绍46. Permutations, 47. Permutations II，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

Given a collection of distinct numbers, return all possible permutations.

For example,
[1,2,3] have the following permutations:
[
[1,2,3],
[1,3,2],
[2,1,3],
[2,3,1],
[3,1,2],
[3,2,1]
]

无重复数据的排列组合：
isVisited 的前后变化很重要

vector<vector<int>> permute(vector<int>& nums) {vector<vector<int>> res;vector<int> tempres;vector<bool> isVisited(nums.size(), false);helper(nums, res, tempres, isVisited);return res;
}
void helper(vector<int>& nums, vector<vector<int>>& res, vector<int>& tempres, vector<bool>& isVisited) {if (tempres.size() == nums.size()) {res.push_back(tempres);return;}for (int i = 0; i < nums.size(); i++) {if (isVisited[i] == true) continue;tempres.push_back(nums[i]);isVisited[i] = true;helper(nums, res, tempres, isVisited);tempres.pop_back();isVisited[i] = false;}return;
}

1. permutation II
   Given a collection of numbers that might contain duplicates, return all possible unique permutations.

For example,
[1,1,2] have the following unique permutations:
[
[1,1,2],
[1,2,1],
[2,1,1]
]

有重复数据的排列组合，必须要事前sort一下，然后保证同一个位置上枚举的数不是同一个。

vector<vector<int>> permuteUnique(vector<int>& nums) {sort(nums.begin(), nums.end());vector<vector<int>> res;vector<int> tempres;vector<bool> isVisited(nums.size(), false);helper(nums, res, tempres, isVisited);return res;
}
void helper(vector<int>& nums, vector<vector<int>>& res, vector<int>& tempres, vector<bool>& isVisited) {if (tempres.size() == nums.size()) {res.push_back(tempres);return;}int lastnum = nums[0] - 1;for (int i = 0; i < nums.size(); i++) {if (isVisited[i] == true || nums[i] == lastnum) continue;tempres.push_back(nums[i]);isVisited[i] = true;lastnum = nums[i];helper(nums, res, tempres, isVisited);tempres.pop_back();isVisited[i] = false;}return;
}

这篇关于46. Permutations, 47. Permutations II的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！

---