Start learning free

LESSON 353 OF 536 · BACKTRACKING

Permutations in Java: Backtracking with a used Array

Practice O(n · n!) Read the full explanation

Given an array nums of distinct integers, return every permutation of nums: every way to put all of its numbers in a row, each number exactly once.

Return the permutations in the order you get by filling the positions from first to last and always trying the numbers in their order in nums: every permutation that starts with nums[0] comes first, then every one that starts with nums[1], and so on. Among the permutations with the same first number, the second number decides the same way, trying the numbers that are left in their order in nums; then the third, and so on. So nums itself always comes first, and nums reversed comes last.

 

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]]
Explanation: Two permutations start with 1, then two with 2, then two with 3.
After 1, the numbers left are 2 and 3, tried in that order, so [1,2,3] comes before [1,3,2].

Example 2:

Input: nums = [3,1,2]
Output: [[3,1,2],[3,2,1],[1,3,2],[1,2,3],[2,3,1],[2,1,3]]
Explanation: The numbers are tried in their order in nums, 3 then 1 then 2, not in ascending order.
After 1, the numbers left are 3 and 2, in that order in nums, so [1,3,2] comes before [1,2,3].

Example 3:

Input: nums = [1]
Output: [[1]]
Explanation: One number can be put in a row in only one way.

 

Constraints:

  • 1 <= nums.length <= 8
  • -10 <= nums[i] <= 10
  • All the numbers in nums are distinct.

Note:

The tutorial uses backtracking. Build a permutation one position at a time in a list current, and keep an array used of true/false values, one per number, that says which numbers current already holds. For the next position, go through the numbers in order and skip the used ones; for each unused number, take it (mark it used and add it to current), fill the remaining positions with a recursive call, then give it back (remove it and mark it unused) so the next number can take its place. When current holds all n numbers, save a copy of it. Trying the numbers in their order in nums gives exactly the order above.

There are n! permutations. Copying each one takes n steps, and the calls that build them, fewer than e · n! in all, each loop over the n numbers, so the time is O(n · n!). Besides the answer, the extra space is O(n): current, used and one call per position.

STEP 1 OF 14
    Ctrl + Enter to check

    JAVA · BACKTRACKING

    Permutations in Java, explained

    Problem overview

    The method permute receives an int[] called nums of distinct integers and returns every permutation: every way to put all the numbers in a row, each exactly once.

    The order of the permutations is fixed. The positions are filled from first to last, always trying the numbers in their order in nums. Every permutation starting with nums[0] comes first, then those starting with nums[1], and so on, and the same rule applies to the second position inside each group. For [1, 2, 3]:

    [[1, 2, 3], [1, 3, 2], [2, 1, 3], [2, 3, 1], [3, 1, 2], [3, 2, 1]]

    The numbers are tried in their order in nums, not in ascending order. For [3, 1, 2] the result is [[3, 1, 2], [3, 2, 1], [1, 3, 2], [1, 2, 3], [2, 3, 1], [2, 1, 3]], which starts with nums itself and ends with nums reversed. For [1] it is [[1]].

    Approach: fill one position at a time

    A permutation of n numbers has n positions. The first can hold any of the n numbers, the second any of the n - 1 that are left, and so on. That gives n! permutations, and any solution has to produce all of them.

    Backtracking builds one permutation position by position. It keeps three things:

    • a list current, the permutation built so far;
    • a boolean[] called used, with one entry per number, saying whether nums[i] is already in current;
    • the result list that collects the finished permutations.

    To fill the next position, go through the numbers from index 0 and skip the used ones. For each free number, take it (mark it used, add it to current), fill the remaining positions with a recursive call, then give it back (remove it, unmark it) so the next number can take its place. When current holds all n numbers, save a copy of it. Because the loop always starts at 0 and goes up, the permutations come out in the order the statement describes.

    The undo steps are the "back" in backtracking. The same current and used are shared by all the calls, so each call has to leave them as it found them.

    Step by step

    1. Create result as a List<List<Integer>> holding a new ArrayList<>().
    2. Create used with new boolean[nums.length]. A new boolean array starts with every element false.
    3. Start the search: backtrack(nums, used, new ArrayList<>(), result). Nothing is placed yet and every number is free.
    4. Return result, which the helper has filled.
    5. Write the helper. backtrack returns void and takes nums, used, current and result. Each call places one more number and calls itself for the rest.
    6. Stop when current.size() == nums.length. The list holds every number once, so it is a whole permutation.
    7. Save a copy, new ArrayList<>(current), and return. The shared current will change, so the result needs its own snapshot.
    8. Loop with i from 0 while i < nums.length: the numbers that could fill the next position, always in the order of nums.
    9. Skip used numbers. If used[i] is true, continue goes on to the next i.
    10. Mark it: set used[i] to true, so deeper calls won't take it.
    11. Add it to the end of current.
    12. Recurse to fill the remaining positions. Nothing needs passing except the same four arguments.
    13. Remove it: current.remove(current.size() - 1) drops the last number.
    14. Unmark it: set used[i] back to false, so later permutations can use that number in another position.

    The solution in Java

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

    void backtrack(int[] nums, boolean[] used, List<Integer> current, List<List<Integer>> result) {
        if (current.size() == nums.length) {
            result.add(new ArrayList<>(current));
            return;
        }
        for (int i = 0; i < nums.length; i++) {
            if (used[i]) {
                continue;
            }
            used[i] = true;
            current.add(nums[i]);
            backtrack(nums, used, current, result);
            current.remove(current.size() - 1);
            used[i] = false;
        }
    }
}

    Java details worth a closer look:

    • boolean[] and shared state. Arrays and lists are passed to methods by reference, so every call works on the same used and current. That is why the undo lines matter.
    • Copy before saving. result.add(current) without the copy stores the one shared list. After the search it is empty, so the call on [1, 2, 3] returns six empty lists: [[], [], [], [], [], []].
    • remove(int). With an int argument, List.remove removes the element at that index. current.size() - 1 is the index of the last element. For a List<Integer> and a value you'd write remove(Integer.valueOf(x)) instead.
    • continue. It skips the rest of the loop body for this i only. The loop itself carries on with the next index.

    Complexity

    Time: O(n * n!). There are n! permutations, and copying each takes n steps. The calls that build them are fewer than e * n! in all, and each loops over the n numbers, which stays within the same bound.

    Space: O(n) besides the answer. The helper keeps current, used and one call per position, so everything is at most n long or deep.

    Edge cases and common mistakes

    • One number. [1] gives [[1]]: one number can be placed only one way.
    • Two numbers. [-10, 10] gives [[-10, 10], [10, -10]]. Negative values need no special care.
    • The size. With 8 numbers, the largest input allowed, the method returns 40320 permutations.
    • Not unmarking. If used[i] = false is left out, numbers stay marked after their first use and the search stops finding most permutations. For [1, 2, 3] that version returns only [[1, 2, 3]].
    • Not removing from current. The list grows past nums.length, so the size check no longer matches and results are wrong.
    • Not copying. The result holds the same list many times, as shown above.
    • Starting the loop above 0. Numbers before the start index could never fill later positions, and some permutations would be missing.

    Testing

    • nums = [1, 2, 3] gives [[1, 2, 3], [1, 3, 2], [2, 1, 3], [2, 3, 1], [3, 1, 2], [3, 2, 1]].
    • nums = [3, 1, 2] gives [[3, 1, 2], [3, 2, 1], [1, 3, 2], [1, 2, 3], [2, 3, 1], [2, 1, 3]].
    • nums = [1] gives [[1]].
    Keep going with Java500+ step-by-step lessons, from your first line of code to coding interviews. Free to start.
    Start learning free