[LeetCode] Different Ways to Add Parentheses

Given a string of numbers and operators, return all possible results from computing all the different possible ways to group numbers and operators. The valid operators are +,- and *.

Example 1

Input: "2-1-1".

((2-1)-1) = 0
(2-(1-1)) = 2

Output: [0, 2]

Example 2

Input: "2*3-4*5"

(2*(3-(4*5))) = -34
((2*3)-(4*5)) = -14
((2*(3-4))*5) = -10
(2*((3-4)*5)) = -10
(((2*3)-4)*5) = 10

Output: [-34, -14, -10, -10, 10]

Analysis:

Divide and conquer

class Solution {
    void calculate(vector<int>&res, vector<int>&l,
                   vector<int>&r, char op)
    {
        for(auto e:l)
        {
            for(auto m:r)
            {
                if(op == '+') res.push_back(e+m);
                else if(op == '-') res.push_back(e-m);
                else if(op == '*') res.push_back(e*m);
                else if(op == '/') {
                    if(m!=0)res.push_back(e/m);
                    else res.push_back(e>0?INT_MAX:INT_MIN);
                }
            }
        }
    }
    void solve(vector<int> &res,  const string & input)
    {
        bool found = false;
        for(int i=1;i<input.length();i++)
        {
            if(input[i] == '+' || input[i] == '-'  
                || input[i] == '*' || input[i] == '/')
            {
                vector<int> l, r;
                solve(l, input.substr(0,i));
                solve(r, input.substr(i+1));
                if(!found) found = true;
                calculate(res, l, r, input[i]);
            }
        }
        
        if(!found) res.push_back(stoi(input));
    }
    
public:
    vector<int> diffWaysToCompute(string input) {
        vector<int> res;
        solve(res, input);
        return res;
    }
};

[LeetCode] Subsets II

Given a collection of integers that might contain duplicates, nums, 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 nums = [1,2,2], a solution is:

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

class Solution {
public:
    vector<vector<int>> subsetsWithDup(vector<int>& nums) {
        vector<vector<int>> res(1);
        sort(nums.begin(), nums.end());
        int lastSize;
        for(int i=0;i<nums.size();i++)
        {
            int start = 0;
            int size = res.size();
            if(i>0 && nums[i] == nums[i-1])
            {
                start = size - lastSize;
            }
            for(int j=start;j<size;j++)
            {
                vector<int> tmp = res[j];
                tmp.push_back(nums[i]);
                res.push_back(tmp);
            }
            lastSize = size - start;
        }
        return res;
    }
};

[LeetCode] Gray Code

The gray code is a binary numeral system where two successive values differ in only one bit.

Given a non-negative integer n representing the total number of bits in the code, print the sequence of gray code. A gray code sequence must begin with 0.

For example, given n = 2, return [0,1,3,2]. Its gray code sequence is:

00 - 0
01 - 1
11 - 3
10 - 2

Note:
For a given n, a gray code sequence is not uniquely defined.

For example, [0,2,3,1] is also a valid gray code sequence according to the above definition.

For now, the judge is able to judge based on one instance of gray code sequence. Sorry about that.

class Solution {
public:
    vector<int> grayCode(int n) {
        vector<int> origin({0});
        for(int i=1;i<=n;i++)
        {
            int size = origin.size();
            int f = 1<<(i-1);
            for(int k=size-1;k>=0;k--)
            {
                origin.push_back(origin[k]|f);
            }
        }
        return origin;
    }
};

[LeetCode] Unique Binary Search Trees II

Given n, generate all structurally unique BST's (binary search trees) that store values 1...n.

For example,
Given n = 3, your program should return all 5 unique BST's shown below.

   1         3     3      2      1
    \       /     /      / \      \
     3     2     1      1   3      2
    /     /       \                 \
   2     1         2                 3

/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode(int x) : val(x), left(NULL), right(NULL) {}
 * };
 */
class Solution {
public:
    void generate(vector<TreeNode*> &res, int num, int offset)
    {
        if(0 == num) 
        {
            res.push_back(NULL);
            return;
        }
        if(1 == num)
        {
            TreeNode* node = new TreeNode(num+offset);
            res.push_back(node);
            return;
        }
        for(int i=1;i<=num;i++)
        {
            vector<TreeNode*> left, right;
            generate(left, i - 1, offset);
            generate(right, num - i, offset + i );
            
            for(int j=0;j<left.size();j++)
            {
                for(int k=0;k<right.size();k++)
                {
                    TreeNode *cur = new TreeNode(i+offset);
                    cur->left = left[j];
                    cur->right = right[k];
                    res.push_back(cur);
                }
            }
        }
        
    }
    vector<TreeNode*> generateTrees(int n) {
        vector<TreeNode*> res;
        generate(res, n, 0);
        return res;
    }
};

[LeetCode] Unique Binary Search Trees

Given n, how many structurally unique BST's (binary search trees) that store values 1...n?

For example,
Given n = 3, there are a total of 5 unique BST's.

   1         3     3      2      1
    \       /     /      / \      \
     3     2     1      1   3      2
    /     /       \                 \
   2     1         2                 3

class Solution {
public:
    int numTrees(int n) 
    {
        vector<int> num(n+1,0);
        num[0] = 1;
        num[1] = 1;
        for(int j=2;j<=n;j++)
        {
            int res = 0;
            for(int i=1;i<=j;i++)
            {
                res += num[j-i]*num[i-1];
            }
            num[j] = res;
        }
        return num[n];
    }
};

[LeetCode] Combinations

Given two integers n and k, return all possible combinations of k numbers out of 1 ... n.

For example,
If n = 4 and k = 2, a solution is:

[
  [2,4],
  [3,4],
  [2,3],
  [1,2],
  [1,3],
  [1,4],
]

This is solution is not efficient, but interesting.

class Solution {
public:
    vector<vector<int> > combine(int n, int k) {
        vector<vector<int> > res;
        if(n == 1)
        {
            res.push_back(vector<int>({1}));
            return res;
        }
        if(k == 1) n++;
        for(int i=1;i<n;i++)
        {
            res.push_back(vector<int>({i}));   
        }
        for(int j=1;j<k;j++)
        {
            int size = res.size();
            for(int i=0;i<size;i++)
            {
                for(int w=res[i][j-1]+1;w<=n;w++)
                {
                    res.push_back(res[i]);
                    res[res.size()-1].push_back(w);
                }
            }
            res.erase(res.begin(), res.begin() + size);
        }
        return res;
    }
};

Backtracing

class Solution {
public:
    vector<vector<int> > combine(int n, int k)
    {
        vector<vector<int>> res;
        vector<int> vec;
        generate(1, n,k,res,vec);
        return res;
    }

    void generate(int start, int n, int k, 
            vector<vector<int>>& res, vector<int>& vec) 
    {
        if(k==0)
        {
            res.push_back(vec);
            return;
        } 
        for(int i=start;i<=n;i++) 
        {
            vec.push_back(i);
            generate(i+1,n,k-1,res,vec);
            vec.pop_back();
        }
    }
};

[LeetCode] Generate Parentheses

Given n pairs of parentheses, write a function to generate all combinations of well-formed parentheses.

For example, given n = 3, a solution set is:

"((()))", "(()())", "(())()", "()(())", "()()()"

DFS Solution:

class Solution {
public:
    void generate(vector<string> & res, string one, 
                  int left, int right, int n)
    {
        if(left == n && right == n)
        {
            res.push_back(one);
            return;
        }
        if(left < n)
        {
            generate(res, one+'(', left+1,right, n);
        }
        if(left > right)
        {
            generate(res, one +')', left,right+1, n);
        }
    }

    vector<string> generateParenthesis(int n) 
    {
        vector<string> res;
        generate(res, "", 0,0,n);
        return res;
    }
};

BFS Solution :
find the last occurrence position P of '(' in the previous result, and append '(' + the rest + ')' to it from P+1 to end;

class Solution {
public:
    vector<string> generateParenthesis(int n) 
    {
        vector<string> res;
        res.push_back("");
        for(int i=0;i<n;i++)
        {
            vector<string> tmp;
            for(int j=0;j<res.size();j++)
            {
                int pos = res[j].rfind('(');
                for(int k=pos+1;k<=res[j].size();k++)
                {
                    tmp.push_back(res[j].substr(0,k) +
                        '(' + res[j].substr(k) + ')');
                }
            }
            res = tmp;
        }
        return res;
    }
};

[LeetCode/LintCode] Letter Combinations of a Phone Number

Given a digit string, return all possible letter combinations that the number could represent.

A mapping of digit to letters (just like on the telephone buttons) is given below.

Input:Digit string "23"
Output: ["ad", "ae", "af", "bd", "be", "bf", "cd", "ce", "cf"].

Note:
Although the above answer is in lexicographical order, your answer could be in any order you want.

class Solution {
public:
    vector<string> letterCombinations(string digits) {
        vector<string> res;
        if(digits.length() == 0) return res;
        
        string letters[] = {"1", "abc", "def", "ghi", "jkl", "mno", "pqrs", "tuv", "wxyz"};
        
        res.push_back("");
        for(int i=0;i<digits.length();i++)
        {
            int c = digits[i] - '0' - 1;
            int size = res.size();
            vector<string> tmp;
            
            for(int j=0;j<size;j++)
            {
                for(int k = 0;k<letters[c].length();k++)
                {
                    tmp.push_back(res[j] + letters[c][k]);
                }
            }
            res = tmp;
        }
        return res;
    }
};

[LeetCode] Permutation Sequence

The set [1,2,3,…,n] contains a total of n! unique permutations.

By listing and labeling all of the permutations in order,
We get the following sequence (ie, for n = 3):

1. "123"
2. "132"
3. "213"
4. "231"
5. "312"
6. "321

Given n and k, return the kth permutation sequence.

Note: Given n will be between 1 and 9 inclusive.

class Solution {
public:
    string getPermutation(int n, int k) 
    {
        string res;
        vector<int> num, f;
        int t = 1;
        for(int i=1;i<=n;t*=i++)
        {
            num.push_back(i);
            f.push_back(t);
        }
        
        int c, i = 1;
        while(res.length() < n)
        {
            int p = k%f[n-i];
            if(p == 0) c = (k/f[n-i]) -1; 
            else c = (k/f[n-i]);
            k -= c*f[n-i];
            res += num[c] + '0';
            num.erase(c + num.begin());
            i++;
        }
        return res;
    }
};

[LeetCode] 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].

Similar with Permutations I, next_permutation can be used to iterate all the permutations. A recursive solution is given as well. Simple non-recursive solution:

class Solution {
public:    
    vector<vector<int> > permute(vector<int> &num) {
        
        vector<vector<int>> res;
        sort(num.begin(),num.end());
        res.push_back(num);
        
        while ( next_permutation(num.begin(),num.end()))
        {
            res.push_back(num);
        } 

        return res;
    }
};

Use the implementation of next_permutation:

class Solution {
public:    
    vector<vector<int> > permute(vector<int> &num) {
        
        vector<vector<int>> res;
        sort(num.begin(),num.end());
        res.push_back(num);
        
        auto s = num.begin();
        auto e = num.end();
        auto i = e - 1;

        while(i != s)
        {
            auto j = i--;
            if(*i < *j)
            {
                auto k = e;
                while(*i >= *--k);
                
                iter_swap(i, k);
                reverse(j, e);
                res.push_back(num);
                i = e - 1;
            }
        }
        
        return res;
    }
};

Recursive solution:

class Solution {
public:
    bool hasDuplication(vector<int> &num, 
                        int start, int end)
    {
        for(int i=start; i<end; i++)
        {
            if(num[i] == num[end]) return true;
        }
        return false;
    }
    
    void permutation(vector<int> &num, 
                    int start, 
                    int end, 
                    vector<vector<int>> &res)
    {
        if(start == end)
        {
            res.push_back(num);
            return;
        }
        for(int i=start; i<=end; i++)
        {
            if(hasDuplication(num, start, i)) continue;
            swap(num[start], num[i]);
            permutation(num, start+1, end, res);
            swap(num[start], num[i]);
        }
    }

    vector<vector<int> > permuteUnique(vector<int> &num) {
        vector<vector<int>> res;
        permutation(num, 0, num.size()-1, res);
        return res;
    }
};

[LeetCode] Permutations I

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].

Simple non-recursive solution:

class Solution {
public:    
    vector<vector<int> > permute(vector<int> &num) {
        
        vector<vector<int>> res;
        sort(num.begin(),num.end());
        res.push_back(num);
        
        while ( next_permutation(num.begin(),num.end()))
        {
            res.push_back(num);
        } 

        return res;
    }
};

Use the implementation of next_permutation:

class Solution {
public:    
    vector<vector<int> > permute(vector<int> &num) {
        
        vector<vector<int>> res;
        sort(num.begin(),num.end());
        res.push_back(num);
        
        auto s = num.begin();
        auto e = num.end();
        auto i = e - 1;

        while(true && i != s)
        {
            auto j = i--;
            if(*i < *j)
            {
                auto k = e;
                while(*i >= *--k);
                
                iter_swap(i, k);
                reverse(j, e);
                res.push_back(num);
                i = e - 1;
            }
        }
        
        return res;
    }
};

Recursive solution:

class Solution {
public:

    void helper(vector<int>& stack, vector<int>& visited, 
                vector<int> &num, vector<vector<int>> &res)
    {
        int size = num.size();

        if(stack.size() == size)
        {
            res.push_back(stack);
            return;
        }
        
        for(int i=0;i<size;i++)
        {
            if(visited[i] == 0)
            {
                stack.push_back(num[i]);
                visited[i] = 1;
                helper(stack, visited, num, res);
                stack.pop_back();
                visited[i] = 0;
            }
        }

    }
    vector<vector<int> > permute(vector<int> &num) {
        
        vector<int> stack;
        vector<vector<int>> res;
        vector<int> visited (num.size(), 0);
        helper(stack,visited, num, res);
        return res;
    }

};

[LeetCode] Combination Sum I

Given a set of candidate numbers (C) and a target number (T), find all unique combinations in C where the candidate numbers sums to T.

The same repeated number may be chosen from C unlimited number of times.

Note:

• All numbers (including target) will be positive integers.
• Elements in a combination (a1, a2, … , ak) must be in non-descending order. (ie, a1 ≤ a2 ≤ … ≤ ak).
• The solution set must not contain duplicate combinations.

For example, given candidate set 2,3,6,7 and target 7,
A solution set is:
[7]
[2, 2, 3] 

class Solution {
public:
    void calc(vector<vector<int> >&res, vector<int>&one,
            vector<int> &candidates,
            int s, int target)
    {
        if(0 == target) res.push_back(one);
        for(int i=s;i<candidates.size() && candidates[i] <= target;i++)
        {
            one.push_back(candidates[i]);
            calc(res, one, candidates, i, target-candidates[i]);
            one.pop_back();
        }
    }
    vector<vector<int> > combinationSum(vector<int> &candidates, int target) 
    {
        sort(candidates.begin(), candidates.end());
        vector<vector<int> > res;
        vector<int> one;
        calc(res, one, candidates, 0, target);
        return res;
    }
};

[LeetCode] Combination Sum II

Given a collection of candidate numbers (C) and a target number (T), find all unique combinations in C where the candidate numbers sums toT.

Each number in C may only be used once in the combination.

Note:

• All numbers (including target) will be positive integers.
• Elements in a combination (a1, a2, … , ak) must be in non-descending order. (ie, a1 ≤ a2 ≤ … ≤ ak).
• The solution set must not contain duplicate combinations.

For example, given candidate set 10,1,2,7,6,1,5 and target 8,
A solution set is:
[1, 7]
[1, 2, 5]
[2, 6]
[1, 1, 6]

Note: how to remove the duplicate combination?

class Solution {
public:
    void calc(vector<vector<int> >&res, vector<int> &candidates, 
              int target, vector<int> & row, int s)
    {
        if(target == 0)
        {
            res.push_back(row);
            return;
        }
        for(int k = s;k<candidates.size() && target >= candidates[k];k++)
        {
            //if there are duplicate elements in the same loop
            //skip them, for it's already handled in previous BT
            if(k!=s && candidates[k-1] == candidates[k]) continue;
            row.push_back(candidates[k]);
            calc(res, candidates, target-candidates[k], row, k+1);
            row.pop_back();
        }
    }
    vector<vector<int> > combinationSum2(vector<int> &candidates, 
                                         int target) 
    {
        vector<vector<int> > res;
        vector<int> row;
        sort(candidates.begin(), candidates.end());
        calc(res, candidates, target, row, 0);
        return res;
    }
};