Skip to content

46 Permutations ✅

Leetcode

Given an array nums of distinct integers, return all the possible permutations. You can return the answer in any order.

alt

Example 1:

Input: nums = [1,2,3]
Output: [[1,2,3],[1,3,2],[2,1,3],[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]]

C# Solution

using System;
using System.Collections.Generic;

namespace Algorithms.Medium
{
  public class Permutation
  {
    public static List<List<int>> Permute(List<int> vs)
    {
      var result = new List<List<int>>();
      bool[] visited = new bool[vs.Count];

      DFSPermute(vs, result, new List<int>(), visited);
      return result;
    }

    private static void DFSPermute(List<int> vs, List<List<int>> result, List<int> curr, bool[] visited)
    {
      if (curr.Count == vs.Count)
      {
        result.Add(new List<int>(curr));
        return;
      }
      for (var i = 0; i < vs.Count; i++)
      {
        if (visited[i] == false)
        {
          visited[i] = true;
          curr.Add(vs[i]);

          DFSPermute(vs, result, curr, visited);

          curr.RemoveAt(curr.Count - 1);
          visited[i] = false;
        }
      }
    }
  }
}

C# Tests

using System.Collections.Generic;
using Algorithms.Medium;
using Xunit;

namespace AlgorithmTests.Medium
{
  public class PermutationTests
  {
    [Fact]
    public void PermuteTest1()
    {
      Assert.Equal(new List<List<int>> {
        new List<int> { 1, 2, 3 },
        new List<int> { 1, 3, 2 },
        new List<int> { 2, 1, 3 },
        new List<int> { 2, 3, 1 },
        new List<int> { 3, 1, 2 },
        new List<int> { 3, 2, 1 } }, Permutation.Permute(new List<int> { 1, 2, 3 }));
    }


    [Fact]
    public void PermuteTest2()
    {
      Assert.Equal(new List<List<int>> {
        new List<int> { 0, 1 },
        new List<int> { 1, 0 } }, Permutation.Permute(new List<int> { 0, 1 }));
    }


    [Fact]
    public void PermuteTest3()
    {
      Assert.Equal(new List<List<int>> {
        new List<int> { 1 } }, Permutation.Permute(new List<int> { 1 }));
    }
  }
}

Note: without visited flag we can check the curr list itself

if(curr.Contains(v[i])){
  continue;
}

Follow-up : what if the given set contains duplicates?

It is very similar to subsets with duplicates problem, except the order of the list is required. Here, we allocate a new boolean array to keep track of whether an element has been used in backtracking.

JS Permutation

(function (exports) {
    'use strict';
    var permutations = (function () {

      var res;

      function swap(arr, i, j) {
        var temp = arr[i];
        arr[i] = arr[j];
        arr[j] = temp;
      }

      function permutations(arr, current) {
        if (current >= arr.length) {
          return res.push(arr.slice());
        }
        for (var i = current; i < arr.length; i += 1) {
          swap(arr, i, current);
          permutations(arr, current + 1);
          swap(arr, i, current);
        }
      }

      /**
      * Finds all the permutations of given array.<br><br>
      * Permutation relates to the act of rearranging, or permuting,
      * all the members of a set into some sequence or order.
      * For example there are six permutations of the set {1,2,3}, namely:
      * (1,2,3), (1,3,2), (2,1,3), (2,3,1), (3,1,2), and (3,2,1).<br><br>
      * Complexity: O(N*N!).
      *
      * @example
      *
      * var permutations = require('path-to-algorithms/src/' +
      * 'combinatorics/permutations').permutations;
      * var result = permutations(['apple', 'orange', 'pear']);
      *
      * // [ [ 'apple', 'orange', 'pear' ],
      * //   [ 'apple', 'pear', 'orange' ],
      * //   [ 'orange', 'apple', 'pear' ],
      * //   [ 'orange', 'pear', 'apple' ],
      * //   [ 'pear', 'orange', 'apple' ],
      * //   [ 'pear', 'apple', 'orange' ] ]
      * console.log(result);
      *
      * @module combinatorics/permutations
      * @public
      * @param {Array} arr Array to find the permutations of.
      * @returns {Array} Array containing all the permutations.
      */
      return function (arr) {
        res = [];
        permutations(arr, 0);
        var temp = res;
        // Free the extra memory
        res = null;
        return temp;
      };
    }());

    exports.permutations = permutations;

  }((typeof window === 'undefined') ? module.exports : window));