LeetCode 46: Permutations Solution | Backtracking in C++
Problem Statement
Given an array nums of distinct integers, return all possible permutations. You can return the answer in any order.
Example:
Input:
nums = [1,2,3]
Output:
[
[1,2,3],
[1,3,2],
[2,1,3],
[2,3,1],
[3,1,2],
[3,2,1]
]
Constraints:
1 <= nums.length <= 6-10 <= nums[i] <= 10- All the integers in
nums are unique.
Optimal Approach: Backtracking
Explanation:
- Backtracking:
- Swap elements to create permutations.
- Recurse with the next index.
- Swap back to restore order.
- Base Condition: If we reach the last index, store the permutation.
C++ Implementation (LeetCode-Compatible)
#include <vector>
using namespace std;
class Solution {
public:
void backtrack(vector<int>& nums, int start, vector<vector<int>>& result) {
if (start == nums.size()) {
result.push_back(nums);
return;
}
for (int i = start; i < nums.size(); i++) {
swap(nums[start], nums[i]);
backtrack(nums, start + 1, result);
swap(nums[start], nums[i]); // Backtrack
}
}
vector<vector<int>> permute(vector<int>& nums) {
vector<vector<int>> result;
backtrack(nums, 0, result);
return result;
}
};
Step-by-Step Explanation
- Recursive Backtracking Approach:
- Start with an empty permutation.
- Swap elements and move forward.
- Swap back (backtrack) to restore order.
- Store results when reaching the base case.
Dry Run Example:
Input:
nums = [1,2,3]
Execution Steps:
| Step |
Current Permutation |
Swaps |
| 1 |
[1,2,3] |
Initial |
| 2 |
[1,2,3] |
Swap(1,1) |
| 3 |
[1,3,2] |
Swap(2,3) |
| 4 |
[2,1,3] |
Swap(1,2) |
| 5 |
[2,3,1] |
Swap(2,3) |
| 6 |
[3,2,1] |
Swap(1,3) |
| 7 |
[3,1,2] |
Swap(2,3) |
Alternative Approaches & Why Not?
| Approach |
Time Complexity |
Space Complexity |
Why Not Optimal? |
| Brute Force (Generate & Check) |
O(N!) |
O(N) |
Inefficient for larger N |
Using STL next_permutation() |
O(N! * N) |
O(1) |
Extra sorting operations |
| Lexicographic Order |
O(N!) |
O(1) |
Difficult to implement manually |
STL next_permutation() Approach (Alternative)
#include <vector>
#include <algorithm>
using namespace std;
class Solution {
public:
vector<vector<int>> permute(vector<int>& nums) {
vector<vector<int>> result;
sort(nums.begin(), nums.end());
do {
result.push_back(nums);
} while (next_permutation(nums.begin(), nums.end()));
return result;
}
};
Why is STL Less Optimal?
- Uses
next_permutation, which modifies and sorts the array.
- Less intuitive for interview explanations.
Best Solution & Why?
| Approach |
Time Complexity |
Space Complexity |
Best Choice? |
| Backtracking (Recursive Swap) |
O(N!) |
O(N) |
✅ Best balance |
STL next_permutation() |
O(N! * N) |
O(1) |
❌ Extra sorting |
| Brute Force |
O(N!) |
O(N) |
❌ Not scalable |
Why is Backtracking Best?
- Generates all permutations efficiently ✅
- Minimal extra space usage ✅
- Easy to explain & implement ✅
Conclusion
- Best Solution: Backtracking (Recursive Swap Method).
- Why? Efficient O(N!) time complexity, intuitive, and widely used.
- Alternative Solutions: STL
next_permutation() (slower), Brute Force (too slow).
Practice More:
