Question

Formatted question description: https://leetcode.ca/all/46.html

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

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]]

Constraints:

1 <= nums.length <= 6
-10 <= nums[i] <= 10
All the integers of nums are unique.

Algorithm

When n=1, there is only one number a1 in the array, and there is only one total permutation, which is a1

When n=2, there is a1a2 in the array at this time, and there are two kinds of full arrays, a1a2 and a2a1. Then, considering the relationship with the above situation at this time, you can find that it is actually added in the two positions before and after a1. A2

When n=3, there are a1a2a3 in the array. At this time, there are six kinds of full arrays, namely a1a2a3, a1a3a2, a2a1a3, a2a3a1, a3a1a2, and a3a2a1. Then according to the above conclusion, it is actually obtained by adding a3 at different positions on the basis of a1a2 and a2a1.

_ a1 _ a2 _: a3a1a2, a1a3a2, a1a2a3

_ a2 _ a1 _: a3a2a1, a2a3a1, a2a1a3

Code

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

public class Permutations {

	public static void main(String[] args) {
		Permutations out = new Permutations();
        Solution_iteration s = out.new Solution_iteration();

		System.out.println(s.permute(new int[]{1, 2, 3}));
	}

	// time: O(N)
	// space: O(N)
	public class Solution_iteration {
	    public List<List<Integer>> permute(int[] nums) {

	        List<List<Integer>> list = new ArrayList<>();

	        if (nums == null || nums.length == 0) {
	            return list;
	        }

	        list.add(new ArrayList<Integer>()); // add empty single list, to make below loop going

	        for (int i = 0; i < nums.length; i++) {
	            List<List<Integer>> tmpList = new ArrayList<>();

	            int insertNum = nums[i];

	            // get each permutations. eg, [1,2], [2,1]
	            for (List<Integer> singlePerm: list) {

	                // eg. [1,2] and insert 3, there are 3 insert position
	                int singleListSize = singlePerm.size();
	                for (int index = 0; index <= singleListSize; index++) { // @note: the usage of arraylist add() api: add(atIndex, value)
	                    singlePerm.add(index, insertNum);
	                    tmpList.add(new ArrayList<Integer>(singlePerm));

	                    // @note: don't forget roll back
	                    singlePerm.remove(index);
	                }
	            }

	            // update list. @note: possible issue, this is not deep copy
	            list = tmpList;
	        }

	        return list;
	    }
	}

    // time: O(N)
    // space: O(N)
    class Solution_dfs {

        List<List<Integer>> result = new ArrayList<>();

        public List<List<Integer>> permute(int[] nums) {

            if (nums == null || nums.length == 0) {
                return result;
            }

            dfs(nums, new HashSet<Integer>(), new ArrayList<Integer>()); // hashset 或者是boolean[]

            return result;
        }

        private void dfs(int[] nums, HashSet<Integer> isVisited, ArrayList<Integer> onePath) {

            if (isVisited.size() == nums.length) {
                result.add(new ArrayList<>(onePath));
                return;
            }

            for (int i = 0; i < nums.length; i++) {
                if (!isVisited.contains(i)) {

                    isVisited.add(i);
                    onePath.add(nums[i]);

                    dfs(nums, isVisited, onePath);

                    isVisited.remove(i);
                    onePath.remove(onePath.size() - 1);
                }
            }
        }
    }

}

############

class Solution {
    private List<List<Integer>> ans = new ArrayList<>();
    private List<Integer> t = new ArrayList<>();
    private boolean[] vis;
    private int[] nums;

    public List<List<Integer>> permute(int[] nums) {
        this.nums = nums;
        vis = new boolean[nums.length];
        dfs(0);
        return ans;
    }

    private void dfs(int i) {
        if (i == nums.length) {
            ans.add(new ArrayList<>(t));
            return;
        }
        for (int j = 0; j < nums.length; ++j) {
            if (!vis[j]) {
                vis[j] = true;
                t.add(nums[j]);
                dfs(i + 1);
                t.remove(t.size() - 1);
                vis[j] = false;
            }
        }
    }
}

// OJ: https://leetcode.com/problems/permutations/
// Time: O(N!)
// Space: O(N)
class Solution {
    vector<vector<int>> ans;
    void dfs(vector<int> &nums, int start) {
        if (start == nums.size() - 1) {
            ans.push_back(nums);
            return;
        }
        for (int i = start; i < nums.size(); ++i) {
            swap(nums[i], nums[start]);
            dfs(nums, start + 1);
            swap(nums[i], nums[start]);
        }
    }
public:
    vector<vector<int>> permute(vector<int>& nums) {
        dfs(nums, 0);
        return ans;
    }
};

'''
remove an element by its value from a set

>>> my_set = {1, 2, 3, 4, 5}
>>> my_set.remove(3)
>>> print(my_set)
{1, 2, 4, 5}

------

cannot remove an element by index from a set in Python3
need to convert the set to a list

>>> my_set = {1, 2, 3, 4, 5}
>>> my_list = list(my_set)
>>> del my_list[2] # remove the element at index 2
>>> my_set = set(my_list)
>>> print(my_set)
{1, 2, 4, 5}
'''

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

        if nums is None or len(nums) == 0:
            return ans

        for num in nums:
            new_res = []
            for perm in res:
                for i in range(len(perm) + 1):
                    new_perm = perm[:i] + [num] + perm[i:]
                    new_res.append(new_perm)

            res = new_res

        return res


class Solution: # iterative, single_perm.insert(index, num)
    def permute(self, nums: List[int]) -> List[List[int]]:
        ans = [[]]

        if nums is None or len(nums) == 0:
            return ans

        for num in nums:
            tmp_list = []

            for single_perm in ans:
                for index in range(len(single_perm) + 1):
                    single_perm.insert(index, num)
                    tmp_list.append(single_perm.copy())
                    single_perm.pop(index)

            ans = tmp_list

        return ans

'''
In Python 3, both the discard() and remove() methods of a set object are used to remove an element from the set, but there is one key difference:

* discard() removes the specified element from the set if it is present, but does nothing if the element is not present.
* remove() removes the specified element from the set if it is present, but raises a KeyError exception if the element is not present.


>>> a
{33, 66, 11, 44, 22, 55}
>>> a.discard(22)
>>> a
{33, 66, 11, 44, 55}

>>> a.discard(200)
>>>
>>> a.remove(200)
Traceback (most recent call last):
  File "<stdin>", line 1, in <module>
KeyError: 200
'''

'''
>>> v1 = set([])
>>> v2 = set()
>>>
>>> v1
set()
>>> v2
set()
'''
class Solution:
    def permute(self, nums: List[int]) -> List[List[int]]:
        res = []
        visited = set([])

        def dfs(nums, path, res, visited):
            if len(path) == len(nums):
                res.append(path + [])
                return
    
            for i in range(0, len(nums)):
                if i not in visited:
                    visited.add(i)
                    path.append(nums[i])
                    dfs(nums, path, res, visited)
                    path.pop()
                    visited.discard(i) # remove(i) will throw exception if i not existing

        dfs(nums, [], res, visited)
        return res

############

class Solution:
    def permute(self, nums: List[int]) -> List[List[int]]:
        def dfs(i):
            if i == n:
                ans.append(t[:])
                return
            for j in range(n):
                if not vis[j]:
                    vis[j] = True
                    t[i] = nums[j]
                    dfs(i + 1)
                    vis[j] = False

        n = len(nums)
        vis = [False] * n
        t = [0] * n
        ans = []
        dfs(0)
        return ans

func permute(nums []int) (ans [][]int) {
	n := len(nums)
	t := make([]int, n)
	vis := make([]bool, n)
	var dfs func(int)
	dfs = func(i int) {
		if i == n {
			cp := make([]int, n)
			copy(cp, t)
			ans = append(ans, cp)
			return
		}
		for j, v := range nums {
			if !vis[j] {
				vis[j] = true
				t[i] = v
				dfs(i + 1)
				vis[j] = false
			}
		}
	}
	dfs(0)
	return
}

function permute(nums: number[]): number[][] {
    const n = nums.length;
    const res: number[][] = [];
    const dfs = (i: number) => {
        if (i === n) {
            res.push([...nums]);
        }
        for (let j = i; j < n; j++) {
            [nums[i], nums[j]] = [nums[j], nums[i]];
            dfs(i + 1);
            [nums[i], nums[j]] = [nums[j], nums[i]];
        }
    };
    dfs(0);
    return res;
}

/**
 * @param {number[]} nums
 * @return {number[][]}
 */
var permute = function (nums) {
    const n = nums.length;
    const ans = [];
    const t = [];
    const vis = new Array(n).fill(false);
    function dfs(i) {
        if (i >= n) {
            ans.push([...t]);
            return;
        }
        for (let j = 0; j < n; ++j) {
            if (!vis[j]) {
                vis[j] = true;
                t.push(nums[j]);
                dfs(i + 1);
                vis[j] = false;
                t.pop();
            }
        }
    }
    dfs(0);
    return ans;
};

public class Solution {
    public IList<IList<int>> Permute(int[] nums) {
        var ans = new List<IList<int>>();
        var t = new List<int>();
        var vis = new bool[nums.Length];
        dfs(nums, 0, t, vis, ans);
        return ans;
    }

    private void dfs(int[] nums, int i, IList<int> t, bool[] vis, IList<IList<int>> ans) {
        if (i >= nums.Length) {
            ans.Add(new List<int>(t));
            return;
        }
        for (int j = 0; j < nums.Length; ++j) {
            if (!vis[j]) {
                vis[j] = true;
                t.Add(nums[j]);
                dfs(nums, i + 1, t, vis, ans);
                t.RemoveAt(t.Count - 1);
                vis[j] = false;
            }
        }
    }
}

impl Solution {
    fn dfs(i: usize, nums: &mut Vec<i32>, res: &mut Vec<Vec<i32>>) {
        let n = nums.len();
        if i == n {
            res.push(nums.clone());
            return;
        }
        for j in i..n {
            nums.swap(i, j);
            Self::dfs(i + 1, nums, res);
            nums.swap(i, j);
        }
    }

    pub fn permute(mut nums: Vec<i32>) -> Vec<Vec<i32>> {
        let mut res = vec![];
        Self::dfs(0, &mut nums, &mut res);
        res
    }
}

46 - Permutations

Question

Algorithm

Code

All Problems

All Solutions

Welcome to Subscribe On Youtube

Question

Algorithm

Code

All Problems

All Solutions