Problem overview
The method countPermutations(int n) returns how many permutations of length n exist. A permutation here is an ordering of the numbers 1 to n, each used exactly once. For n = 3 there are six: [1, 2, 3], [1, 3, 2], [2, 1, 3], [2, 3, 1], [3, 1, 2] and [3, 2, 1], so the answer is 6.
The function only has to return the count, not the permutations. That distinction matters: the count of permutations of n items is n! (n factorial), and it can be computed with a single loop, while listing the permutations takes a time proportional to n! itself. The statement limits n to 12.
Approach: build the count from the previous length
Let dp[i] be the number of permutations of length i. To build a permutation of length i, pick its first element: there are i choices. Whatever you pick, the other i - 1 positions are filled with the remaining i - 1 numbers in any order, and there are dp[i - 1] ways to do that. So:
dp[i] = i * dp[i - 1]
The recurrence needs a starting value. There is exactly one permutation of length 0, the empty one, so dp[0] = 1. Then dp[1] = 1 * 1 = 1, dp[2] = 2 * 1 = 2, dp[3] = 3 * 2 = 6, and in general dp[i] is i!.
Starting at length 0 rather than 1 has a practical benefit: for n = 0 the table has just the index 0, and the answer dp[0] = 1 is already there, with no special case.
Step by step
- Create the table.
vector<int> dp(n + 1)has indices 0 ton, sodp[n]exists. A vector created with only a size is filled with zeros. - Set the base case.
dp[0] = 1. - Loop upwards.
iruns from 1 toninclusive. Filling the table in increasing order meansdp[i - 1]is final by the timedp[i]needs it. - Apply the recurrence inside the loop:
dp[i] = i * dp[i - 1]. - Return
dp[n].
The solution in C++
class Solution {
public:
int countPermutations(int n) {
vector<int> dp(n + 1);
dp[0] = 1;
for (int i = 1; i <= n; i++) {
dp[i] = i * dp[i - 1];
}
return dp[n];
}
};
Running it gives these results:
n = 0 -> 1
n = 1 -> 1
n = 2 -> 2
n = 3 -> 6
n = 5 -> 120
n = 12 -> 479001600
The C++ detail that matters here is the size of int. 12! = 479001600 fits in a 32-bit int (maximum 2147483647), but 13! = 6227020800 does not. Signed integer overflow is undefined behaviour in C++, not a harmless wrap-around, so the limit n <= 12 in the statement is what keeps this code correct. For larger n, use long long, which holds up to 20!.
Complexity
Time: O(n). One loop with one multiplication per iteration.
Space: O(n). The table holds n + 1 integers. Since each entry only needs the previous one, a single running variable would reduce this to O(1), but the table makes the recurrence easy to see.
Listing the permutations in C++
Many people searching for "permutation in C++" want the permutations themselves, not the count. The standard library has std::next_permutation in <algorithm>. It rearranges a range into the next ordering in lexicographic order and returns false after the last one. Start from a sorted range to visit every permutation:
vector<int> v = {1, 2, 3};
do {
for (int x : v) cout << x << ' ';
cout << '\n';
} while (next_permutation(v.begin(), v.end()));
1 2 3
1 3 2
2 1 3
2 3 1
3 1 2
3 2 1
If the range does not start sorted, next_permutation only produces the orderings that come after it. For {3, 1, 2} it gives 3 1 2 and 3 2 1 only. Sort first, or use a recursive backtracking function that tries every unused value at each position. Either way, the loop body runs n! times, so listing all permutations is only practical for small n (about 10 or 11 at most).
Edge cases and common mistakes
n = 0. The answer is 1, not 0. The vector has one element and the loop never runs.- Looping with
i < n. The last entrydp[n]would stay 0. The condition must bei <= n. - Sizing the vector as
n.dp[n]would be out of bounds, and C++ does not check; the program reads or writes memory it doesn't own. - Overflow beyond 12.
13!does not fit inint. Switch the vector and return type tolong longif the limit grows. - Confusing counting with generating. Producing every permutation is what costs
n!time; counting them costsnsteps.
