46. All permutations

46_solution1_loop.c

#include <stdlib.h>
#include <string.h>

static void swap(int *a, int *b) {
  int t = *a;
  *a = *b;
  *b = t;
}

static void backtrack(int *cur, int n, int idx, int **result, int *returnSize) {
  if (idx == n) {
    result[*returnSize] = malloc(n * sizeof(int));
    memcpy(result[(*returnSize)++], cur, n * sizeof(int));
    return;
  }

  for (int i = idx; i < n; i++) {
    swap(&cur[idx], &cur[i]);
    backtrack(cur, n, idx + 1, result, returnSize);
    swap(&cur[idx], &cur[i]);
  }
}

int **permute(int *nums, int numsSize, int *returnSize,
              int **returnColumnSizes) {
  int total = 1;
  for (int i = 2; i <= numsSize; i++)
    total *= i;

  int **result = malloc(total * sizeof(int *));
  *returnColumnSizes = malloc(total * sizeof(int));
  for (int i = 0; i < total; i++)
    (*returnColumnSizes)[i] = numsSize;
  *returnSize = 0;

  int *cur = malloc(numsSize * sizeof(int));
  memcpy(cur, nums, numsSize * sizeof(int));
  backtrack(cur, numsSize, 0, result, returnSize);
  free(cur);
  return result;
}

46_solution2_fullyrecursive.c

#include <stdlib.h>
#include <string.h>

static void swap(int *a, int *b) {
  int t = *a;
  *a = *b;
  *b = t;
}

static void backtrack(int *nums, int n, int idx, int i, int **result,
                      int *returnSize) {
  if (idx == n) {
    result[*returnSize] = malloc(n * sizeof(int));
    memcpy(result[(*returnSize)++], nums, n * sizeof(int));
    return;
  }
  if (i == n)
    return;

  // choose nums[i] for position idx, then fix the next position
  swap(&nums[idx], &nums[i]);
  backtrack(nums, n, idx + 1, idx + 1, result, returnSize);
  swap(&nums[idx], &nums[i]); // undo

  // try the next candidate for the same position
  backtrack(nums, n, idx, i + 1, result, returnSize);
}

int **permute(int *nums, int numsSize, int *returnSize,
              int **returnColumnSizes) {
  int total = 1;
  for (int i = 2; i <= numsSize; i++)
    total *= i;

  int **result = malloc(total * sizeof(int *));
  *returnColumnSizes = malloc(total * sizeof(int));
  for (int i = 0; i < total; i++)
    (*returnColumnSizes)[i] = numsSize;
  *returnSize = 0;

  backtrack(nums, numsSize, 0, 0, result, returnSize);
  return result;
}

46_solution1_loop.cpp

#include <utility>
#include <vector>

using namespace std;

class Solution {
public:
  vector<vector<int>> permute(vector<int> &nums) {
    vector<vector<int>> result;
    vector<int> cur(nums.begin(), nums.end());
    backtrack(nums, result, cur, 0);
    return result;
  }

  void backtrack(vector<int> &nums, vector<vector<int>> &result,
                 vector<int> &cur, int idx) {
    if (idx == nums.size()) {
      result.push_back(cur);
      return;
    }

    for (int i = idx; i < nums.size(); i++) {
      swap(cur[idx], cur[i]);
      backtrack(nums, result, cur, idx + 1);
      swap(cur[idx], cur[i]);
    }
  }
};

46_solution2_fullyrecursive.cpp

#include <utility>
#include <vector>

using namespace std;

class Solution {
public:
  vector<vector<int>> permute(vector<int> &nums) {
    vector<vector<int>> result;
    backtrack(nums, result, 0, 0);
    return result;
  }

  void backtrack(vector<int> &nums, vector<vector<int>> &result, int idx,
                 int i) {
    if (idx == nums.size()) {
      result.push_back(nums);
      return;
    }
    if (i == nums.size())
      return;

    // choose nums[i] for position idx, then fix the next position
    swap(nums[idx], nums[i]);
    backtrack(nums, result, idx + 1, idx + 1);
    swap(nums[idx], nums[i]); // undo

    // try the next candidate for the same position
    backtrack(nums, result, idx, i + 1);
  }
};

46_solution1_loop.go

package backtracking

func permute(nums []int) [][]int {
    var result [][]int
    cur := append([]int(nil), nums...)

    var backtrack func(idx int)
    backtrack = func(idx int) {
        if idx == len(cur) {
            result = append(result, append([]int(nil), cur...))
            return
        }

        for i := idx; i < len(cur); i++ {
            cur[idx], cur[i] = cur[i], cur[idx]
            backtrack(idx + 1)
            cur[idx], cur[i] = cur[i], cur[idx]
        }
    }

    backtrack(0)
    return result
}

46_solution2_fullyrecursive.go

package backtracking

func permute(nums []int) [][]int {
    var result [][]int

    var backtrack func(idx, i int)
    backtrack = func(idx, i int) {
        if idx == len(nums) {
            result = append(result, append([]int(nil), nums...))
            return
        }
        if i == len(nums) {
            return
        }

        // choose nums[i] for position idx, then fix the next position
        nums[idx], nums[i] = nums[i], nums[idx]
        backtrack(idx+1, idx+1)
        nums[idx], nums[i] = nums[i], nums[idx] // undo

        // try the next candidate for the same position
        backtrack(idx, i+1)
    }

    backtrack(0, 0)
    return result
}

46_solution1_loop.java

import java.util.ArrayList;
import java.util.List;

class Solution {
    public List<List<Integer>> permute(int[] nums) {
        List<List<Integer>> result = new ArrayList<>();
        backtrack(nums.clone(), result, 0);
        return result;
    }

    private void backtrack(int[] cur, List<List<Integer>> result, int idx) {
        if (idx == cur.length) {
            List<Integer> perm = new ArrayList<>(cur.length);
            for (int x : cur) {
                perm.add(x);
            }
            result.add(perm);
            return;
        }

        for (int i = idx; i < cur.length; i++) {
            swap(cur, idx, i);
            backtrack(cur, result, idx + 1);
            swap(cur, idx, i);
        }
    }

    private void swap(int[] a, int i, int j) {
        int t = a[i];
        a[i] = a[j];
        a[j] = t;
    }
}

46_solution2_fullyrecursive.java

import java.util.ArrayList;
import java.util.List;

class Solution {
    public List<List<Integer>> permute(int[] nums) {
        List<List<Integer>> result = new ArrayList<>();
        backtrack(nums, result, 0, 0);
        return result;
    }

    private void backtrack(int[] nums, List<List<Integer>> result, int idx, int i) {
        if (idx == nums.length) {
            List<Integer> perm = new ArrayList<>(nums.length);
            for (int x : nums) {
                perm.add(x);
            }
            result.add(perm);
            return;
        }
        if (i == nums.length) {
            return;
        }

        // choose nums[i] for position idx, then fix the next position
        swap(nums, idx, i);
        backtrack(nums, result, idx + 1, idx + 1);
        swap(nums, idx, i); // undo

        // try the next candidate for the same position
        backtrack(nums, result, idx, i + 1);
    }

    private void swap(int[] a, int i, int j) {
        int t = a[i];
        a[i] = a[j];
        a[j] = t;
    }
}

46_solution1_loop.js

/**
 * @param {number[]} nums
 * @return {number[][]}
 */
var permute = function (nums) {
  const result = [];
  const cur = [...nums];

  const backtrack = (idx) => {
    if (idx === cur.length) {
      result.push([...cur]);
      return;
    }

    for (let i = idx; i < cur.length; i++) {
      [cur[idx], cur[i]] = [cur[i], cur[idx]];
      backtrack(idx + 1);
      [cur[idx], cur[i]] = [cur[i], cur[idx]];
    }
  };

  backtrack(0);
  return result;
};

46_solution2_fullyrecursive.js

/**
 * @param {number[]} nums
 * @return {number[][]}
 */
var permute = function (nums) {
  const result = [];

  const backtrack = (idx, i) => {
    if (idx === nums.length) {
      result.push([...nums]);
      return;
    }
    if (i === nums.length) return;

    // choose nums[i] for position idx, then fix the next position
    [nums[idx], nums[i]] = [nums[i], nums[idx]];
    backtrack(idx + 1, idx + 1);
    [nums[idx], nums[i]] = [nums[i], nums[idx]]; // undo

    // try the next candidate for the same position
    backtrack(idx, i + 1);
  };

  backtrack(0, 0);
  return result;
};

46_solution1_loop.py

from typing import List


class Solution:
    def permute(self, nums: List[int]) -> List[List[int]]:
        result: List[List[int]] = []
        cur = nums[:]

        def backtrack(idx: int) -> None:
            if idx == len(cur):
                result.append(cur[:])
                return

            for i in range(idx, len(cur)):
                cur[idx], cur[i] = cur[i], cur[idx]
                backtrack(idx + 1)
                cur[idx], cur[i] = cur[i], cur[idx]

        backtrack(0)
        return result

46_solution2_fullyrecursive.py

from typing import List


class Solution:
    def permute(self, nums: List[int]) -> List[List[int]]:
        result: List[List[int]] = []

        def backtrack(idx: int, i: int) -> None:
            if idx == len(nums):
                result.append(nums[:])
                return
            if i == len(nums):
                return

            # choose nums[i] for position idx, then fix the next position
            nums[idx], nums[i] = nums[i], nums[idx]
            backtrack(idx + 1, idx + 1)
            nums[idx], nums[i] = nums[i], nums[idx]  # undo

            # try the next candidate for the same position
            backtrack(idx, i + 1)

        backtrack(0, 0)
        return result

46_solution1_loop.rs

impl Solution {
    pub fn permute(nums: Vec<i32>) -> Vec<Vec<i32>> {
        let mut result = Vec::new();
        let mut cur = nums.clone();
        Self::backtrack(&mut result, &mut cur, 0);
        result
    }

    fn backtrack(result: &mut Vec<Vec<i32>>, cur: &mut Vec<i32>, idx: usize) {
        if idx == cur.len() {
            result.push(cur.clone());
            return;
        }

        for i in idx..cur.len() {
            cur.swap(idx, i);
            Self::backtrack(result, cur, idx + 1);
            cur.swap(idx, i);
        }
    }
}

46_solution2_fullyrecursive.rs

impl Solution {
    pub fn permute(mut nums: Vec<i32>) -> Vec<Vec<i32>> {
        let mut result = Vec::new();
        Self::backtrack(&mut nums, &mut result, 0, 0);
        result
    }

    fn backtrack(nums: &mut Vec<i32>, result: &mut Vec<Vec<i32>>, idx: usize, i: usize) {
        if idx == nums.len() {
            result.push(nums.clone());
            return;
        }
        if i == nums.len() {
            return;
        }

        // choose nums[i] for position idx, then fix the next position
        nums.swap(idx, i);
        Self::backtrack(nums, result, idx + 1, idx + 1);
        nums.swap(idx, i); // undo

        // try the next candidate for the same position
        Self::backtrack(nums, result, idx, i + 1);
    }
}