5,332
edits
No edit summary |
|||
Line 17: | Line 17: | ||
* [https://leetcode.com/problems/single-number-ii/ single-number-ii] | * [https://leetcode.com/problems/single-number-ii/ single-number-ii] | ||
* [https://leetcode.com/problems/single-number-iii/ single-number-iii] | * [https://leetcode.com/problems/single-number-iii/ single-number-iii] | ||
====Permutations==== | |||
Print all permutations of an array.<br> | |||
The idea here is that you need a for-loop nested for each element of an array.<br> | |||
So n element means n nested for-loops. You use recursion to nest the loops.<br> | |||
* [https://leetcode.com/problems/permutations/ Permutations] | |||
* [https://leetcode.com/problems/permutations-ii/ Permutations-iii] | |||
{{ hidden | Permute Brute-force solution | |||
A more advanced solution would use backtracking, however it is time-consuming to implement for an interview.<br> | |||
Here is a quick brute-force solution. | |||
* Enumerate all possible n^n numbers from 000 to 999 and then filter out number with duplicate digits | |||
<syntaxhighlight lang="cpp"> | |||
class Solution { | |||
public: | |||
vector<vector<int>> permute(vector<int>& nums) { | |||
vector<vector<int>> ans; | |||
vector<int> indices(nums.size()); | |||
permuteHelper(nums, indices, 0, ans); | |||
return ans; | |||
} | |||
bool isValid(vector<int>& indices) { | |||
vector<char> check(indices.size(), false); | |||
for (int i = 0; i < indices.size(); i++) { | |||
if (check[indices[i]]) { | |||
return false; | |||
} | |||
check[indices[i]] = true; | |||
} | |||
return true; | |||
} | |||
void permuteHelper(vector<int>& nums, vector<int>& indices, | |||
int col, vector<vector<int>>& ans) { | |||
if (col == nums.size()) { | |||
if (isValid(indices)) | |||
print(nums, indices, ans); | |||
return; | |||
} | |||
for (int i = 0; i < nums.size(); i++) { | |||
indices[col] = i; | |||
permuteHelper(nums, indices, col+1, ans); | |||
} | |||
} | |||
void print(vector<int>& nums, vector<int>& indices, vector<vector<int>>& ans) { | |||
vector<int> new_nums(nums.size()); | |||
for (int i = 0; i < nums.size(); i++) { | |||
new_nums[i] = nums[indices[i]]; | |||
} | |||
ans.push_back(new_nums); | |||
} | |||
}; | |||
</syntaxhighlight> | |||
}} |