Start learning free

LESSON 352 OF 535 · BACKTRACKING

Permutations in C++: Backtracking with a used Vector

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

Given a vector 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 a vector 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 15
    Ctrl + Enter to check

    C++ · BACKTRACKING

    Permutations in C++, explained

    Problem overview

    The function permute receives a vector<int> named nums of distinct integers and returns every permutation of it: every way to put all of its numbers in a row, each exactly once, as a vector<vector<int>>.

    The order of the answer is fixed. The positions are filled from first to last, and the numbers are always tried in their order in nums. All permutations that start with nums[0] come first, then those that start with nums[1], and so on, and inside a group the second number decides the same way. So nums itself is always first and nums reversed is last.

    For nums = {1, 2, 3} the answer is:

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

    For nums = {3, 1, 2} the numbers are tried in the order 3, 1, 2, not in ascending order, so the answer is:

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

    A single number, {1}, has one permutation: [[1]].

    Approach: fill one position at a time

    With n distinct numbers there are n! permutations: n choices for the first position, n - 1 for the second, and so on. Any solution has to produce all of them, so the goal is to generate each one exactly once, in the right order, without wasted work.

    Backtracking builds a permutation one position at a time in a vector current. A second vector, used, holds one true-or-false value per number and says which numbers current already contains. To fill the next position:

    • go through the numbers in order, from index 0;
    • skip the used ones;
    • for each free number, take it (mark it used and append it to current), fill the remaining positions with a recursive call, then give it back (remove it and mark it free) so that the next number can try the same position.

    When current holds n numbers, it is a whole permutation, and a copy goes into the result. Because the loop always tries the numbers in their order in nums, the permutations come out in exactly the order the statement describes.

    Step by step

    1. Create result, an empty vector<vector<int>>.
    2. Create used as vector<bool> used(nums.size(), false): the two arguments are the size and the value of every element. used[i] says whether nums[i] is already in the permutation being built.
    3. Create current, an empty vector<int>. No position is filled yet.
    4. Start the search with backtrack(nums, used, current, result). Every number is still free.
    5. Return result, which the helper has filled.
    6. Declare the helper backtrack inside the class, returning void, with all four vectors passed by reference, because it changes three of them and the caller must see the changes.
    7. Check whether current is full: current.size() == nums.size(). A full current holds every number once.
    8. Save and return: push_back(current) stores a copy in result.
    9. Loop over every index i from 0 to nums.size() - 1. Starting at 0 every time is what gives the required order.
    10. Skip used numbers: if used[i] is true, continue. A number can't appear twice.
    11. Mark it: set used[i] to true, so deeper calls won't take it again.
    12. Append it: current.push_back(nums[i]) fills the next position.
    13. Recurse to fill the remaining positions. This call finds every permutation that starts with what current now holds.
    14. Undo the append with current.pop_back().
    15. Undo the mark: set used[i] back to false, so permutations built later can use nums[i] in another position.

    The solution in C++

    class Solution {
public:
    vector<vector<int>> permute(vector<int>& nums) {
        vector<vector<int>> result;
        vector<bool> used(nums.size(), false);
        vector<int> current;
        backtrack(nums, used, current, result);
        return result;
    }

    void backtrack(vector<int>& nums, vector<bool>& used, vector<int>& current, vector<vector<int>>& result) {
        if (current.size() == nums.size()) {
            result.push_back(current);
            return;
        }
        for (int i = 0; i < nums.size(); i++) {
            if (used[i]) {
                continue;
            }
            used[i] = true;
            current.push_back(nums[i]);
            backtrack(nums, used, current, result);
            current.pop_back();
            used[i] = false;
        }
    }
};

    The C++ details worth a closer look:

    • vector<bool> is special. The standard library packs it into single bits, so used[i] returns a small proxy object instead of a bool&. Reading it in an if and assigning true or false to it work as expected, which is all this code does. You can't take a normal bool& from it, though.
    • The constructor vector<bool> used(nums.size(), false) builds nums.size() elements, each false. Writing vector<bool> used(nums.size()) would also give false everywhere, but spelling it out shows the intent.
    • References. nums, used, current and result all travel by reference. Passing used or current by value would copy them at every call, and passing result by value would leave the caller's result empty.
    • push_back(current) copies the vector, so the saved permutation isn't affected when current changes afterwards.
    • current.size() == nums.size() compares two unsigned values, so there is no sign mix. The loop's i < nums.size() compares an int with an unsigned value: that is safe while i is non-negative, and some compilers warn about it.
    • continue skips the rest of the loop body for the current i and moves on to i + 1. The i++ in the loop header still runs.

    Complexity

    Time: O(n · n!). There are n! permutations, and copying each into the result takes n steps. The recursion makes fewer than e · n! calls in all, and each call loops over the n numbers, so the work for the whole search stays within a constant factor of n · n!.

    Space: O(n) extra. Besides the answer, the program holds current, used and one call per position, each of size at most n.

    Edge cases and common mistakes

    • Forgetting to unmark used[i]. After the first permutation every number stays marked, so nothing else can be built. For {1, 2, 3} the function returns only [[1,2,3]].
    • Forgetting pop_back(). current stays full after the first permutation, so its size never equals nums.size() again. For {1, 2, 3} the function again returns only [[1,2,3]].
    • Looping from the wrong index. Starting the loop at a later index, as subset-style searches do, skips the numbers before it. A permutation can use any free number in any position, so the loop always starts at 0.
    • Sorting nums first. The statement asks for the numbers in their order in nums. For {3, 1, 2} the answer starts with [3,1,2], not [1,2,3].
    • One number. {1} gives [[1]].
    • Two numbers. {-10, 10} gives [[-10,10],[10,-10]].
    • The biggest input. With 8 numbers the answer has 40,320 permutations. For {1, 2, 3, 4, 5, 6, 7, 8} the first is [1,2,3,4,5,6,7,8] and the last is [8,7,6,5,4,3,2,1].

    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]].
    • nums = {-10, 10} gives [[-10,10],[10,-10]].
    • nums = {1, 2, 3, 4, 5, 6, 7, 8} gives 40,320 permutations, from [1,2,3,4,5,6,7,8] to [8,7,6,5,4,3,2,1].
    Keep going with C++500+ step-by-step lessons, from your first line of code to coding interviews. Free to start.
    Start learning free