Permutations II

Given a collection of numbers that might contain duplicates, return all possible unique permutations. For example, `[1,1,2]` have the following unique permutations: `[1,1,2]`, `[1,2,1]`, and `[2,1,1]`. Problem link Solution

• recursive solution, only when last element is not  (the same and used)
```class Solution {
public:
vector<vector > permuteUnique(vector &num) {
sort(num.begin(), num.end());
vector<vector> vv;
vector v;
vector u(num.size(), false);
rec(vv, v, u, num);
return vv;
}

void rec(vector<vector> &vv, vector &v, vector &u, vector &num){
for (int i=0; i<num.size(); ++i){
if (!u[i] && (i==0 || i>0 && !(num[i]==num[i-1] && !u[i-1]))){
v.push_back(num[i]);
u[i] = true;
if (v.size()==num.size()){
vv.push_back(v);
}else{
rec(vv, v, u, num);
}
v.pop_back();
u[i] = false;
}
}
}
};
```

Permutations

Given a collection of 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]`, and `[3,2,1]`.

Solution

• backtrack with stack
```class Solution {
public:
vector<vector<int> > permute(vector<int> &num) {
vector< vector<int> > vv;
int i;
unsigned n=num.size();
vector<int> v;
vector<bool> used(n, false);

i=0;
while (true){
// only stop the loop when it is at level zero and i goes over
v.push_back(i);
used[i]=true;
for (i=0; i<n; i++){// looks for next available position to select
if (used[i]==false){
break;
}
}
if (v.size()==n){
// a complete sequence is generated, backtrack
vector<int> tmp;
for (int j=0; j<v.size(); j++){
tmp.push_back(num[v[j]]);
}
vv.push_back(tmp);
int j;
do{
j=v.back();
v.pop_back();
used[j]=false;
for (++j; j<n; ++j){// starting from current indices, looks for next available position to select
if (used[j]==false){
break;
}
}
}while(j>=n&&!v.empty()|| (j<n&&used[j]));
if (j>=n&&v.empty()){
break;
}
i=j;
}
}
return vv;
}
};
```

Recursive solution

• use an auxiliary array to track whether the current element has been used in the current permutation
```class Solution {
public:
vector<vector<int> > permute(vector<int> &num) {
vector<vector<int>> vv;
vector<bool> u(num.size(), false); // used or
vector<int> v;
rec(vv, v, u, num);
return vv;
}

void rec(vector<vector<int>> &vv, vector<int> &v, vector<bool> &u, vector<int> &num){
for (int i=0; i<num.size(); i++){
if (!u[i]){ // if i is not used
v.push_back(num[i]);
u[i] = true;
if (v.size()==num.size()){
vv.push_back(v);
}else{
rec(vv, v, u, num);
}
v.pop_back();
u[i] = false;
}
}
}
};
```

Factorial Trailing Zeroes

Given an integer n, return the number of trailing zeroes in n!.

input n, output the count of how many zeroes at the end of n!. where n! = 1 * 2 * … * n

for example

``````n = 6, n! = 720, answer = 1.
n = 8, n! = 40320, answer = 1.
n = 32, n! = 263130836933693530167218012160000000, answer = 7
``````

Note: Your solution should be in logarithmic time complexity.

Solution

• just count how many 5 factors in the natural number sequence
• be careful about overflow in int, so use long for “base” variable
```class Solution {
public:
int trailingZeroes(int n) {
if (!n) return 0;
int num = 0;
long base = 5;
int l;
while (l = n/base){
num += l;
base*=5;
}
return num;
}
};
```

Unique Paths

A robot is located at the top-left corner of a m x n grid (marked ‘Start’ in the diagram below).

The robot can only move either down or right at any point in time. The robot is trying to reach the bottom-right corner of the grid (marked ‘Finish’ in the diagram below).

How many possible unique paths are there?

Above is a 3 x 7 grid. How many possible unique paths are there?

Note: m and n will be at most 100.

Solution

• the number of possible unique paths is exactly the binomial coefficient ${\choose m+n-2 m-1}$
• use loops rather than computing factorial when calculating the binomial coefficients
```class Solution {
public:
int uniquePaths(int m, int n) {
long long prod = 1;
--m;
--n;
int small = min(m,n);
int big = max(m,n);
for (long long i=big+1; i<=m+n; i++){
prod = prod * i / (i-big);
}
return (int)prod;
}
};
```

Subsets II

Given a collection of integers that might contain duplicates, S, return all possible subsets.

Note:

• Elements in a subset must be in non-descending order.
• The solution set must not contain duplicate subsets.

For example,
If S = `[1,2,2]`, a solution is:

```[
[2],
[1],
[1,2,2],
[2,2],
[1,2],
[]
]```

Solution

• check if previous element is the same when creating a new subset
• similar to combination sum II
```class Solution {
public:
vector<vector<int> > subsetsWithDup(vector<int> &S) {
vector<vector<int> > vv;
sort(S.begin(), S.end());
for (int i=0; i<=S.size(); ++i){
vector<int> v;
rec(S.size(), i, 0, vv, v, S);
}
return vv;
}
void rec(int n, int k, int l, vector<vector<int> > &vv, vector<int> &v, vector<int> S){
if (v.size()==k){
vv.push_back(v);
return;
}
for (int i=l; i<n; ++i){
if (i>l && S[i]==S[i-1]) continue;
v.push_back(S[i]);
rec(n,k,i+1,vv,v,S);
v.pop_back();
}
}
};
```

Subsets

Given a set of distinct integers, S, return all possible subsets.

Note:

• Elements in a subset must be in non-descending order.
• The solution set must not contain duplicate subsets.

For example,
If S = `[1,2,3]`, a solution is:

```[
[3],
[1],
[2],
[1,2,3],
[1,3],
[2,3],
[1,2],
[]
]```

Solution

• a generalization to combinations
• the original array is not sorted
• the indices for recursion runs from 0 to n-1
```class Solution {
public:
vector<vector<int> > subsets(vector<int> &S) {
vector<vector<int> > vv;
sort(S.begin(), S.end());
for (int i=0; i<=S.size(); ++i){
vector<int> v;
rec(S.size(), i, 0, vv, v, S);
}
return vv;
}

void rec(int n, int k, int l, vector<vector<int> > &vv, vector<int> &v, vector<int> S){
if (v.size()==k){
vv.push_back(v);
return;
}
for (int i=l; i<n; ++i){
v.push_back(S[i]);
rec(n,k,i+1,vv,v,S);
v.pop_back();
}
}
};
```

Palindrome Number

Determine whether an integer is a palindrome. Do this without extra space.

Solution

• two pass algorithm: count how many digits first
• negative number are not palindrome
```class Solution {
public:
bool isPalindrome(int x) {
if (x<0) return false;
int down=1;
while (x/down>=10){
//stop when x/down becomes a single digit
down*=10;
}
while (true){
if (x%10!=x/down) return false;
x = x/10;
down = down/10;
if (down==0) return true;
x -= x/down*down;
down = down/10;
if (down==0) return true;
}
return true;
}
};
```

A slightly simpler solution

• could use mod to remove leftmost digit (while divide removes rightmost digit)
```class Solution {
public:
bool isPalindrome(int x) {
if (x<0) return false;
int down=1;
while (x/down>=10){
//stop when x/down becomes a >single digit
down*=10;
}
while (x){
if (x%10!=x/down) return false;
x = x%down/10;
down = down/100;
}
return true;
}
};
```