排列组合总结

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

Notice

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

Have you met this question in a real interview?

Yes

Example

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

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

总结点：

1. make_pair 函数的使用
2. vector 容器支持pop_back()
3. 递归和非递归实现，非递归用到队列，模拟二叉树层序遍历

class Solution {
public:
    /*
     * @param nums: A set of numbers
     * @return: A list of lists
     */
    vector<vector<int>> subsets(vector<int> &nums) {
        // write your code here
        // ensure order
        sort(nums.begin(), nums.end());
        vector<vector<int> > res;
        // vector<int> result;
        // subsets(nums, 0, result, res);
        subsets(nums, res);
        return res;
    }
    void subsets(vector<int> &nums,
                 int pos,
                 vector<int>& result,
                 vector<vector<int>>& res) {
        res.push_back(result);
        for (int i = pos; i < nums.size(); i++) {
            result.push_back(nums[i]);
            subsets(nums, i + 1, result, res);
            result.pop_back();
        }
    }
    void subsets(vector<int> &nums,
                 vector<vector<int>>& res) {
        queue<pair<int, vector<int>>> subs;
        // init with empty
        res.push_back(vector<int>());
        subs.push(make_pair(-1, vector<int>()));
        // start loop
        while (!subs.empty()) {
            pair<int, vector<int>> tmp = subs.front();
            subs.pop();
            vector<int> result = tmp.second;
            int start = tmp.first + 1;
            for (int i = start; i < nums.size(); i++) {
                result.push_back(nums[i]);
                res.push_back(result);
                subs.push(make_pair(i, result));
                result.pop_back();
            }
        }
    }
};

Given a list of numbers that may has duplicate numbers, return all possible subsets

Notice

• Each element in a subset must be in non-descending order.
• The ordering between two subsets is free.
• The solution set must not contain duplicate subsets.

Have you met this question in a real interview?

Yes

Example

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

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

class Solution {
public:
    /*
     * @param nums: A set of numbers.
     * @return: A list of lists. All valid subsets.
     */
    vector<vector<int>> subsetsWithDup(vector<int> &nums) {
        // write your code here
        vector<vector<int>> res;
        // vector<int> result;
        sort(nums.begin(), nums.end());
        // subsets(nums, 0, result, res);
        subsets(nums, res);
        return res;
    }
    void subsets(vector<int> &nums, int pos, vector<int>& result, vector<vector<int>>& res) {
        res.push_back(result);
        for (int i = pos; i < nums.size(); i++) {
            if (i > pos && nums[i] == nums[i - 1]) {
                continue;
            }
            result.push_back(nums[i]);
            subsets(nums, i + 1, result, res);
            result.pop_back();
        }
    }
    void subsets(vector<int>& nums, vector<vector<int>>& res) {
        queue<pair<int, vector<int>>> pairs;
        // init with empty()
        res.push_back(vector<int>());
        pairs.push(make_pair(-1, vector<int>()));
        // loop
        while (!pairs.empty()) {
            pair<int, vector<int>> tmp = pairs.front();
            pairs.pop();
            vector<int> result = tmp.second;
            int start = tmp.first + 1;
            for (int i = start; i < nums.size(); i++) {
                if (i > start && nums[i] == nums[i - 1]) {
                    continue;
                }
                result.push_back(nums[i]);
                res.push_back(result);
                pairs.push(make_pair(i, result));
                result.pop_back();
            }
        }
    }
};

Given a list of numbers, return all possible permutations.

Notice

You can assume that there is no duplicate numbers in the list.

Have you met this question in a real interview?

Yes

Example

For nums = [1,2,3], the permutations are:

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

点题：

1. 非递归实现，next permutation算法
2. 和组合有很大区别，排列用swap

class Solution {
public:
    /*
     * @param nums: A list of integers.
     * @return: A list of permutations.
     */
    vector<vector<int>> permute(vector<int> &nums) {
        // write your code here
        vector<vector<int>> res;
        //permute(nums, 0, res);
        sort(nums.begin(), nums.end());
        bool is_valid = true;
        while (is_valid) {
            res.push_back(nums);
            is_valid = nextPermute(nums);
        }
        return res;
    }
    void permute(vector<int>& nums, int pos, vector<vector<int>>& res) {
        if (pos == nums.size()) {
            res.push_back(nums);
            return;
        }
        for (int i = pos; i < nums.size(); i++) {
            swap(nums[i], nums[pos]);
            permute(nums, pos + 1, res);
            swap(nums[i], nums[pos]);
        }
    }
    bool nextPermute(vector<int>& nums) {
        int n = nums.size() - 1;
        int m = n - 1;
        while (m >= 0 && nums[m] >= nums[m + 1]) {
            m--;
        }
        if (m >= 0) {
            while (nums[n] <= nums[m]) {
                n--;
            }
            swap(nums[m], nums[n]);
        }
        reverse(nums, m + 1, nums.size() - 1);
        // next permute is valid
        if (m < 0) {
            return false;
        } else {
            return true;
        }
    }
    void reverse(vector<int>& nums, int start, int end) {
        while (start < end) {
            swap(nums[start], nums[end]);
            start++;
            end--;
        }
    }
};

Given a list of numbers with duplicate number in it. Find all unique permutations.

Have you met this question in a real interview?

Yes

Example

For numbers [1,2,2] the unique permutations are:

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

点题：

1. 避免重复的话，next permutation自然避免
2. 还有其他两种避免办法，一个是swap的时候，在POS上不能出现两次相同的value
3. 另一个去重算法是一层一层地选，不用swap，用visit标识访问

class Solution {
public:
    /*
     * @param :  A list of integers
     * @return: A list of unique permutations
     */
    vector<vector<int>> permuteUnique(vector<int> &nums) {
        // write your code here
        vector<vector<int>> res;
        vector<int> visit(nums.size(), 0);
        vector<int> result;
        sort(nums.begin(), nums.end());
        // bool is_valid = true;
        // while (is_valid) {
        //     res.push_back(nums);
        //     is_valid = nextPermute(nums);
        // }
        doPermute2(nums, result, visit, res);
        return res;
    }
    void doPermute2(vector<int>& nums, vector<int>& result,
                    vector<int>& visit, vector<vector<int>>& res) {
        if (result.size() == nums.size()) {
            res.push_back(result);
            return;
        }
        for (int i = 0; i < nums.size(); i++) {
            if (visit[i] > 0) {
                continue;
            }
            if (i > 0 && nums[i] == nums[i - 1] && visit[i - 1] == 0) {
                continue;
            }
            result.push_back(nums[i]);
            visit[i] = 1;
            doPermute2(nums, result, visit, res);
            visit[i] = 0;
            result.pop_back();
        }
    }
    void doPermute(vector<int>& nums, int pos, vector<vector<int>>& res) {
        if (pos == nums.size()) {
            res.push_back(nums);
            return;
        }
        for (int i = pos; i < nums.size(); i++) {
            if (!needSwap(nums, i, pos)) {
                continue;
            }
            swap(nums[i], nums[pos]);
            doPermute(nums, pos + 1, res);
            swap(nums[i], nums[pos]);
        }
    }
    bool needSwap(vector<int>& nums, int i, int pos) {
        if (i == pos) {
            return true;
        }
        for (int j = pos; j < i; j++) {
            if (nums[j] == nums[i]) {
                return false;
            }
        }
        return true;
    }
    bool nextPermute(vector<int>& nums) {
        int n = nums.size() - 1;
        int m = n - 1;
        while (m >= 0 && nums[m] >= nums[m + 1]) {
            m--;
        }
        if (m >= 0) {
            while (nums[n] <= nums[m]) {
                n--;
            }
            swap(nums[n], nums[m]);
        }
        reverse(nums, m + 1, nums.size() - 1);
        if (m < 0) {
            return false;
        } else {
            return true;
        }
    }
    void reverse(vector<int>& nums, int start, int end) {
        while (start < end) {
            swap(nums[start], nums[end]);
            start++;
            end--;
        }
    }
};

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.

Notice

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

Have you met this question in a real interview?

Yes

Example

Given candidate set [2,3,6,7] and target 7, a solution set is:

[7]
[2, 2, 3]

class Solution {
public:
    /*
     * @param candidates: A list of integers
     * @param target: An integer
     * @return: A list of lists of integers
     */
    vector<vector<int>> combinationSum(vector<int> &candidates, int target) {
        // write your code here
        vector<vector<int>> res;
        vector<int> result;
        sort(candidates.begin(), candidates.end());
        combinationSum(candidates, target, 0, 0, result, res);
        return res;
    }
    void combinationSum(vector<int> &candidates, int target, int sum, int pos,
                        vector<int>& result, vector<vector<int>>& res) {
        if (sum == target) {
            res.push_back(result);
            return;
        }
        for (int i = pos; i < candidates.size(); i++) {
            sum += candidates[i];
            if (sum > target) {
                break;
            }
            result.push_back(candidates[i]);
            combinationSum(candidates, target, sum, i, result, res);
            sum -= candidates[i];
            result.pop_back();
        }
    }
};

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

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

Notice

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

Have you met this question in a real interview?

Yes

Example

Given candidate set [10,1,6,7,2,1,5] and target 8,

A solution set is:

[
  [1,7],
  [1,2,5],
  [2,6],
  [1,1,6]
]

class Solution {
public:
    /*
     * @param num: Given the candidate numbers
     * @param target: Given the target number
     * @return: All the combinations that sum to target
     */
    vector<vector<int>> combinationSum2(vector<int> &num, int target) {
        // write your code here
        vector<int> result;
        vector<vector<int>> res;
        sort(num.begin(), num.end());
        combinationSum2(num, target, 0, 0, result, res);
        return res;
    }
    void combinationSum2(vector<int> &num, int target, int sum, int pos,
                         vector<int> &result, vector<vector<int>> &res) {
        if (sum == target) {
            res.push_back(result);
            return;
        }
        for (int i = pos; i < num.size(); i++) {
            if (i > pos && num[i] == num[i - 1]) {
                continue;
            }
            sum += num[i];
            if (sum > target) {
                break;
            }
            result.push_back(num[i]);
            combinationSum2(num, target, sum, i + 1, result, res);
            result.pop_back();
            sum -= num[i];
        }
    }
};

Given a string s, partition s such that every substring of the partition is a palindrome.

Return all possible palindrome partitioning of s.

Have you met this question in a real interview?

Yes

Example

Given s = "aab", return:

[
  ["aa","b"],
  ["a","a","b"]
]

class Solution {
public:
    /*
     * @param s: A string
     * @return: A list of lists of string
     */
    vector<vector<string>> partition(string &s) {
        // write your code here
        vector<vector<string>> res;
        vector<string> result;
        partition(s, 0, result, res);
        return res;
    }
    void partition(string &s, int pos, vector<string> &result, vector<vector<string>> &res) {
        if (pos == s.size()) {
            res.push_back(result);
            return;
        }
        for (int i = pos; i < s.size(); i++) {
            string tmp = s.substr(pos, i - pos + 1);
            if (isPalindrome(tmp)) {
                result.push_back(tmp);
                partition(s, i + 1, result, res);
                result.pop_back();
            }
        }
    }
    bool isPalindrome(string &s) {
        int i = 0;
        int j = s.size() - 1;
        while (i < j) {
            if (s[i++] != s[j--]) {
                return false;
            }
        }
        return true;
    }
};

Given a digit string excluded 01, 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.

Notice

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

Have you met this question in a real interview?

Yes

Example

Given "23"

Return ["ad", "ae", "af", "bd", "be", "bf", "cd", "ce", "cf"]

class Solution {
public:
    /*
     * @param digits: A digital string
     * @return: all posible letter combinations
     */
    vector<string> letterCombinations(string &digits) {
        // write your code here
        unordered_map<char, string> maps;
        maps['2'] = "abc";
        maps['3'] = "def";
        maps['4'] = "ghi";
        maps['5'] = "jkl";
        maps['6'] = "mno";
        maps['7'] = "pqrs";
        maps['8'] = "tuv";
        maps['9'] = "wxyz";
        vector<string> res;
        if (digits.size() == 0) {
            return res;
        }
        string result;
        letterCombinations(digits, maps, 0, result, res);
        return res;
    }
    void letterCombinations(string &digits, unordered_map<char, string> &maps,
                            int pos, string &result, vector<string> &res) {
        if (pos == digits.size()) {
            res.push_back(result);
            return;
        }
        string tmp = maps[digits[pos]];
        for (int i = 0; i < tmp.size(); i++) {
            result.push_back(tmp[i]);
            letterCombinations(digits, maps, pos + 1, result, res);
            result.pop_back();
        }
    }
};

Given a string containing only digits, restore it by returning all possible valid IP address combinations.

Have you met this question in a real interview?

Yes

Example

Given "25525511135", return

[
  "255.255.11.135",
  "255.255.111.35"
]

Order does not matter.

点题:

1. IP地址只有四个分割
2. 每个分割都是小于255
3. 0开头的数据只能是一个，不能是两个字符

class Solution {
public:
    /*
     * @param s: the IP string
     * @return: All possible valid IP addresses
     */
    vector<string> restoreIpAddresses(string &s) {
        // write your code here
        vector<string> res;
        restoreIpAddresses(s, 0, 4, "", res);
        return res;
    }
    void restoreIpAddresses(string &s, int pos, int k, string result, vector<string> &res) {
        if (pos == s.size() && k == 0) {
            res.push_back(result.substr(1, result.size() - 1));
            return;
        }
        for (int i = pos; i < s.size(); i++) {
            string tmpstr = s.substr(pos, i - pos + 1);
            int tmpint = stoi(tmpstr);
            if (tmpint > 255 || tmpstr[0] == '0' && i > pos) {
                break;
            }
            restoreIpAddresses(s, i + 1, k - 1, result + "." + tmpstr, res);
        }
    }
};

总结：

1. 非递归实现组合
2. 非递归实现排列
3. 递归必须很精通