Question

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],
  [3,2,1]
]

Solution

• This problem is of same domain as 78. Subsets.
• The idea here is to generate all permutation through recursion.
• We need to keep a track of whether we have included the element in the tempList or not because in case say we added 1, 2, 3 now when recursion unwinds and 3 and 2 is removed from the stack. The for loops moves and generate a call with tempList as 1, 3 now we don't want to add 1 again.
• A general approach can be found in 5.2 of Competitive Programmer's Handbook

void search() {
    if (permutation.size() == n) {
        // process permutation
    } else {
        for (int i = 0; i < n; i++) {
            if (chosen[i]) continue;
            chosen[i] = true;
            permutation.push_back(i);
            search();
            chosen[i] = false;
            permutation.pop_back();
        }
    }
}

Time complexity

Space complexity

O (n) which is the space taken by the stack to keep track and the space taken by the Set to keep track of all possibe unique combination seen so far which in worse case (all unique numbers) will be equal to all possible combinations.
Also the solution uses recursion so it does take some space on call stack.

Notes

• We don't make recursive call after pop since we don't want to generate a subset where any of the elements in nums is not a part as its in the case of combination.