Prototype:

Given an array, find all combinations of the elements in the array rearranged in any order.

The primary version:

Given an array nums that does not contain duplicate digits, return all possible permutations. You can return the answers in any order.

  • Example 1:

Output: input: nums = [1, 2, 3], [[1, 2, 3], [31] 1,,1,3 [2], [2,3,1], [3,1,2], [3, 2, 1]]

  • Example 2:

Input: nums = [0,1] output: [[0,1],[1,0]

  • Example 3:

Input: nums = [1] Output: [[1]

Analysis:

  • The array is n in length, and each digit has n factorial possibilities by permutation and combination:n * (n-1) * (n-2) * ... * 3 * 2 * 1 = n!, n digits, so the time complexity isO(n * n !)
  • Set the possible numbers one by one. Set to the last digit indicates that the permutation and combination is complete
  • Go back to the previous step and repeat the next possible permutation. This is called backtracking: an algorithm that finds all possible solutions by exploring all possible candidates. If the candidate solution is determined not to be a solution (or at least not the last one), the backtracking algorithm will discard the solution by making some change in the previous step, that is, backtracking and trying again.
  • We can swap the numbers we have identified with the numbers that follow, thus narrowing the range of numbers that need to be arranged without additional storage space

The code is as follows:

/ * * *@param {number[]} nums
 * @return {number[][]}* /
var permute = function(nums) {
  let ans = [];
  backtrack(ans, nums, 0, nums.length);
  return ans;
};

var backtrack = function (ans, curArr, idx, leng) {
  if (idx == leng) {
    ans.push(curArr);
    return;
  }

  for (let i = idx; i < leng; i++) {
    [curArr[i], curArr[idx]] = [...swap(curArr[i], curArr[idx])];
    backtrack(ans, curArr.concat([]), idx + 1, leng); [curArr[i], curArr[idx]] = [...swap(curArr[i], curArr[idx])]; }}var swap = function(a, b) {
  a = a ^ b;
  b = a ^ b;
  a = a ^ b;
  return [a, b];
}
Copy the code

premium

Given a sequence nums that can contain repeating digits, return all non-repeating full permutations in any order.

  • Example 1:

Input: nums = [1,1,2] output: [[1,1,2], [2,1]]

  • Example 2:

Output: input: nums = [1, 2, 3], [[1, 2, 3], [31] 1,,1,3 [2], [2,3,1], [3,1,2], [3, 2, 1]]

Analysis:

  • Plan 1: you can first list all the combinations in a non-repetitive way, and then repeat them yourself.
/ * * *@param {number[]} nums
 * @return {number[][]}* /
var permuteUnique = function(nums) {
  let ans = new Set(a); backtrack(ans, nums,0);
  let arr = [...ans];
  
  for (let i = 0; i < arr.length; i++) {
    arr[i] = arr[i].split('+');
    for (let j = 0; j < arr[i].length; j++) {
      arr[i][j] = parseInt(arr[i][j]); }}return arr;
};

var backtrack = function (result, curArray, curIdx) {
  let leng = curArray.length;

  if (curIdx === leng) {
    result.add(curArray.join('+'));
  }

  for (let i = curIdx; i < leng; i++) {
    [curArray[i], curArray[curIdx]] = [...swap(curArray[i], curArray[curIdx])];
    backtrack(result, curArray.concat([]), curIdx + 1); [curArray[i], curArray[curIdx]] = [...swap(curArray[i], curArray[curIdx])]; }}var swap = function (a, b) {
  a = a ^ b;
  b = a ^ b;
  a = a ^ b;
  return [a, b];
}
Copy the code

This method is relatively inefficient and takes 264ms

  • Method 2: We find that if we encounter repeated numbers, the result after combination is the same. If we encounter repeated numbers, we only take the first repeated value to arrange, which can avoid repetition. To implement this approach, two problems need to be solved:
    1. The current element is required first, and the following elements are in ascending order, so that whenever they are repeated, they are next to each other.
    2. We need to cut the combined array into two parts, one is the combined part, the other is the uncombined part, and sort the uncombined part
let sortArr = curArray.slice(curIdx)
sortArr.sort((a, b) = > a - b);
curArray = curArray.slice(0, curIdx).concat(sortArr);
Copy the code
  • Adjacent numbers are easier to determine
if ( (i < leng - 1 && curArray[i] === curArray[i + 1]) {continue;
}
Copy the code

The code is as follows:

/ * * *@param {number[]} nums
 * @return {number[][]}* /
var permuteUnique = function(nums) {
  let ans = [];
  backtrack(ans, nums, 0);
  return ans;
};

var backtrack = function (result, curArray, curIdx) {
  let leng = curArray.length;

  if (curIdx === leng) {
    result.push(curArray);
    return;
  }

  let sortArr = curArray.slice(curIdx);
  sortArr.sort((a, b) = > a - b);
  curArray = curArray.slice(0, curIdx).concat(sortArr);

  for (let i = curIdx; i < leng; i++) {
    if ( (i < leng - 1 && curArray[i] === curArray[i + 1]) {continue;
    }
    
    [curArray[i], curArray[curIdx]] = [...swap(curArray[i], curArray[curIdx])];
    backtrack(result, curArray.concat([]), curIdx + 1); [curArray[i], curArray[curIdx]] = [...swap(curArray[i], curArray[curIdx])]; }}var swap = function (a, b) {
  a = a ^ b;
  b = a ^ b;
  a = a ^ b;
  return [a, b];
}
Copy the code

The execution efficiency of this method is better than that of method 1, and it takes 100ms

premium

Given a positive integer N, we reorder the numbers in any order (including the original order), noting that the leading digit cannot be zero.

Return true if we can get a power of 2 as described above; Otherwise, return false.

  • Example 1:

Input: 1 Output: true

  • Example 2:

Input: 10 Output: false

  • Example 3:

Input: 16 Output: true

  • Example 4:

Input: 24 Output: false

  • Example 5:

Input: 46 Output: true

Analysis:

  • Numbers need to be split into arrays
  • Array full permutation
  • All permutation results are processed, not the first 0
  • Convert the total permutation result to a number and determine whether it is a power of 2

How do you figure out a power of 2? It’s easy to just keep dividing by 2 and get to 1, and take modulo 2 along the way

var isSqrt = function (num) {
  let left = 0, right = num;
  while(num ! =1) {
    if (num % 2! =0) {
      return false;
    }
    num /= 2;
  }
  return true;
}
Copy the code

There is another efficient way to do this: a number n is a power of 2 if and only if n is a positive integer and the binary representation of n contains only one 1. Therefore, we can consider using bitwise operations to extract the lowest 1 in the binary representation of n, and then determine whether the remaining value is 0. Here are two common bitwise manipulation techniques related to “least significant in binary representation.”

  1. “Adjacent bitwise and”
return n > 0 && (n & (n - 1= = =))0;
Copy the code

Where & stands for bitwise and operation. The bitwise manipulation directly removes the least significant binary representation of n, 1

  1. “Take inverse bitwise and”
return n > 0 && (n & -n) == n;
Copy the code

Since negative numbers are stored in the computer according to the rules of complement, the binary representation of -n is the inverse of each bit of the binary representation of N plus 1, and then the sum with n is equal to n.





The code is as follows:

/ * * *@param {number} n
 * @return {boolean}* /
var reorderedPowerOf2 = function(n) {
  let arr = [];
  let value = 0
  while (n) {
    value = n % 10;
    arr.push(value);
    n = Math.floor(n / 10);
  }

  let allPermute = permuteUnique(arr);
  
  let ans = allPermute.some((item) = > {
    item = item.join(' ');
    if (item[0] != '0') {
      item = Number(item);
      if (isSqrt(item)) {
        return true; }}})return ans || false;
};

var permuteUnique = function (nums) {
  let ans = [];
  backtrack(ans, nums, 0);
  return ans;
}

var backtrack = function (result, curArray, curIdx) {
  let leng = curArray.length;

  if (curIdx === leng) {
    result.push(curArray);
    return;
  }

  let sortArr = curArray.slice(curIdx);
  sortArr.sort((a, b) = > a - b );
  curArray = curArray.slice(0, curIdx).concat(sortArr);

  for (let i = curIdx; i < leng; i++) {
    if (i < leng - 1 && curArray[i] === curArray[i + 1]) { continue; }
    [curArray[i], curArray[curIdx]] = [...swap(curArray[i], curArray[curIdx])];
    backtrack(result, curArray.concat([]), curIdx + 1); [curArray[i], curArray[curIdx]] = [...swap(curArray[i], curArray[curIdx])]; }}var swap = function (a, b) {
  a = a ^ b;
  b = a ^ b;
  a = a ^ b;
  return [a, b];
}

var isSqrt = function (n) {
  return n > 0 && (n & (n - 1= = =))0;
}
Copy the code

Now that you’ve seen it, give it a thumbs up