source: https://leetcode.com/problems/permutations/
C/C++ Solution to LeetCode problem 46. Permutations.
Problem
Given an array nums
of distinct integers, return all the possible permutations. You can return the answer in any order.
Examples
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]]
Example 2:
Input: nums = [0,1]
Output: [[0,1],[1,0]]
Example 3:
Input: nums = [1]
Output: [[1]]
Constraints
1 <= nums.length <= 6
-10 <= nums[i] <= 10
- All the integers of
nums
are unique.
Solution
This can be solved using Backtracking (see more backtracking problems)
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
class Solution {
private:
vector<vector<int>> result;
void permutations(vector<int>& nums, int index) {
if (index == nums.size()) {
result.push_back(nums);
return;
}
for (int i=index; i<nums.size(); i++) {
swap(nums[index], nums[i]);
permutations(nums, index+1);
swap(nums[index], nums[i]);
}
}
public:
vector<vector<int>> permute(vector<int>& nums) {
permutations(nums, 0);
return result;
}
};