This is the sixth day of my participation in the November Gwen Challenge. Check out the event details: The last Gwen Challenge 2021
Thank you very much for reading this article ~ welcome 【👍 like 】【⭐ collect 】【📝 comment 】~ Give up is easy, but insist must be cool ~ HOPE we can all make a little progress every day ~ Original ~ https://juejin.cn/user/2771185768884824/posts blog
Sword finger Offer II 083. Full arrangement of set without repeating elements | 46. The whole arrangement:
Given an integer array nums that contains no duplicate digits, return all possible permutations. Answers can be returned in any order.
Sample 1
Output: input: nums = [1, 2, 3], [[1, 2, 3], [31] 1,,1,3 [2], [2,3,1], [3,1,2], [3, 2, 1]]Copy the codeThe sample 2
Input: nums = [0,1] output: [[0,1],[1,0]Copy the codeSample 3
Input: nums = [1] Output: [[1]Copy the codeprompt
- 1 <= nums.length <= 6
- -10 <= nums[i] <= 10
- All integers in NUMs are different
Analysis of the
- This algorithm problem using recursion, backtracking method is relatively simple, who must use cycle non recursion, two master admire.
- The hint says that each number is different, so we can think of all permutations as the location of the number or different permutations of the index of the array, because the numbers are different, so we don’t care what the number of each number is.
- We can create a single space to store intermediate permutations, so we need to be able to determine whether a number has been selected. We can use a hash table to store the result of the current permutation, and then see if it contains the current number, but this seems inefficient.
- The number is different for each location, so we can just store the number in a particular location to see if it’s used.
- Can directly use a Boolean array visited the location of the store, but the prompt says the best digital number six, then we can say the use of six binary all Numbers have been used and unused, an int type variable enough, we use the binary type int variable changes, to the corresponding Numbers have been used and unused.
- You can also swap the array directly to simulate the arrangement of each digit in all positions. Rotate the first position, then rotate the second, and so on.
Answer key
java
Do not exchange
class Solution {
public List<List<Integer>> permute(int[] nums) {
List<List<Integer>> ans = new ArrayList<>();
dfs(nums, new ArrayList<>(nums.length), 0, ans);
return ans;
}
private void dfs(int[] nums, List<Integer> row, int flag, List<List<Integer>> ans) {
if (row.size() == nums.length) {
ans.add(new ArrayList<>(row));
return;
}
for (int i = 0; i < nums.length; ++i) {
if (((flag >> i) & 1) = =0) {
row.add(nums[i]);
dfs(nums, row, flag | (1 << i), ans);
row.remove(row.size() - 1); }}}}Copy the codeUse swaps
class Solution {
public List<List<Integer>> permute(int[] nums) {
List<List<Integer>> ans = new ArrayList<>();
backtrack(nums, 0, ans);
return ans;
}
private void backtrack(int[] nums, int cur, List<List<Integer>> ans) {
if (cur == nums.length) {
ans.add(Arrays.stream(nums).boxed().collect(Collectors.toList()));
return;
}
// The current position remains unchanged, then the next line
backtrack(nums, cur + 1, ans);
// Change one of the following to the current position
for (int i = cur + 1; i < nums.length; ++i) {
swap(nums, cur, i);
backtrack(nums, cur + 1, ans); swap(nums, cur, i); }}private void swap(int[] nums, int a, int b) { nums[a] ^= nums[b]; nums[b] ^= nums[a]; nums[a] ^= nums[b]; }}Copy the codec
/** * Return an array of arrays of size *returnSize. * The sizes of the arrays are returned as *returnColumnSizes array. * Note: Both returned array and *columnSizes array must be malloced, assume caller calls free(). */
int** permute(int* nums, int numsSize, int* returnSize, int** returnColumnSizes){
*returnSize = numsSize;
for (int i = 2; i < numsSize; ++i) {
*returnSize *= i;
}
int **ans = (int* *)malloc(sizeof(int *) * (*returnSize));
*returnColumnSizes = (int *) malloc(sizeof(int) * (*returnSize));
for (int i = 0; i < *returnSize; ++i) {
ans[i] = (int *) malloc(sizeof(int) * numsSize);
(*returnColumnSizes)[i] = numsSize;
}
int ansSize = 0;
backtrack(nums, numsSize, 0, ans, &ansSize);
return ans;
}
void backtrack(int* nums, int numsSize, int cur, int **ans, int *ansSize) {
if (cur == numsSize) {
for (int i = 0; i < numsSize; ++i) {
ans[*ansSize][i] = nums[i];
}
*ansSize += 1;
return;
}
// The current position remains unchanged, then the next line
backtrack(nums, numsSize, cur + 1, ans, ansSize);
// Change one of the following to the current position
for (int i = cur + 1; i < numsSize; ++i) {
swap(nums, cur, i);
backtrack(nums, numsSize, cur + 1, ans, ansSize); swap(nums, cur, i); }}void swap(int* nums, int a, int b) {
nums[a] ^= nums[b];
nums[b] ^= nums[a];
nums[a] ^= nums[b];
}
Copy the codec++
class Solution {
private:
void backtrack(vector<int> &nums, int cur, vector<vector<int>> &ans) {
if (cur == nums.size()) {
ans.push_back(nums);
return;
}
// The current position remains unchanged, then the next line
backtrack(nums, cur + 1, ans);
// Change one of the following to the current position
for (int i = cur + 1; i < nums.size(a); ++i) {swap(nums[cur], nums[i]);
backtrack(nums, cur + 1, ans);
swap(nums[cur], nums[i]); }}public:
vector<vector<int>> permute(vector<int>& nums) {
vector<vector<int>> ans;
backtrack(nums, 0, ans);
returnans; }};Copy the codepython
class Solution:
def permute(self, nums: List[int]) - >List[List[int]] :
n = len(nums)
ans = []
def backtrack(cur: int) - >None:
if cur == n:
ans.append(nums[:])
return
# The current position remains the same, then the next line
backtrack(cur + 1)
Change one of the following to the current position
for i in range(cur + 1, n):
nums[cur], nums[i] = nums[i], nums[cur]
backtrack(cur + 1)
nums[cur], nums[i] = nums[i], nums[cur]
backtrack(0)
return ans
Copy the codego
func permute(nums []int)[] []int {
n := len(nums)
var ans [][]int
var backtrack func(cur int)
backtrack = func(cur int) {
if cur == n {
ans = append(ans, append([]int{}, nums...) )return
}
// The current position remains unchanged, then the next line
backtrack(cur + 1)
// Change one of the following to the current position
for i := cur + 1; i < n; i++ {
nums[cur], nums[i] = nums[i], nums[cur]
backtrack(cur + 1)
nums[cur], nums[i] = nums[i], nums[cur]
}
}
backtrack(0)
return ans
}
Copy the coderust
impl Solution {
pub fn permute(mut nums: Vec<i32- > >)Vec<Vec<i32> > {let mut ans = Vec::new();
Solution::backtrack(&mut nums, 0, &mut ans);
ans
}
fn backtrack(nums: &mut Vec<i32>, cur: usize, ans: &mut Vec<Vec<i32> >) {if cur == nums.len() {
ans.push(nums.clone());
return;
}
// The current position remains unchanged, then the next line
Solution::backtrack(nums, cur + 1, ans);
// Change one of the following to the current position
(cur + 1..nums.len()).for_each(|i| {
nums.swap(cur, i);
Solution::backtrack(nums, cur + 1, ans); nums.swap(cur, i); }); }}Copy the code