Generating all permutations of n elements can be done with backtracking: at each position i, swap arr[i] with each arr[j] (j >= i), recurse to fill position i+1, then swap back (backtrack). This generates all n! permutations in-place with O(n) auxiliary space for the recursion stack.
void permute(vector<int>& arr, int start, vector<vector<int>>& res) {
if(start==arr.size()){res.push_back(arr);return;}
for(int i=start;i<arr.size();i++){
swap(arr[start],arr[i]);
permute(arr,start+1,res);
swap(arr[start],arr[i]);
}
}At position start, try placing each element arr[i] (i>=start) there by swapping. Recurse to fill the rest. After recursion, swap back to restore the array for the next iteration.
The first position can be filled in n ways, the second in n-1 ways, etc. Total permutations = n!. For n=10, that is 3,628,800. For n=20, about 2.4 quintillion — factorial blowup is severe.
For arrays with duplicate elements, skip swapping arr[start] with arr[i] if arr[i] was already placed at position start in a previous iteration. Use a set to track values used at each position.
Quiz coming soon for this algorithm.