Question

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

46. Permutations

Given a collection of distinct numbers, return all possible permutations.

For example,
[1,2,3] have the following permutations:
[1,2,3], [1,3,2], [2,1,3], [2,3,1], [3,1,2], and [3,2,1].

@tag-backtracking

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

Java

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);
                }
            }
        }
    }

}

// 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;
    }
};

class Solution(object):
  def permute(self, nums):
    """
    :type nums: List[int]
    :rtype: 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 > 0 and nums[i - 1] == nums[i]:
        #     continue
        if i not in visited:
          visited.add(i)
          path.append(nums[i])
          dfs(nums, path, res, visited)
          path.pop()
          visited.discard(i)

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

46 - Permutations

Question

Algorithm

Code

All Problems

All Solutions