剑指offer79-87二进制枚举、回溯

剑指 Offer II 079. 所有子集

给定一个整数数组 nums ，数组中的元素 互不相同 。返回该数组所有可能的子集（幂集）。
解集 不能 包含重复的子集。你可以按 任意顺序 返回解集

输入：nums = [1,2,3]
输出：[[],[1],[2],[1,2],[3],[1,3],[2,3],[1,2,3]]

方法一：递归

index由0到n，当前index指向的内容要么加入，要么不加入，对于两种选择分别开辟两条线，让其运行到最后，在每条线里，如果index到了n，那么就将结果加入到容器中

如果加入和不加入反过来，也要将加入的元素删除掉

方法二：二进制枚举

三个元素，那么用三位二进制去假设某个元素有没有，比如 5 2 9 用三位二进制110表示 5 2存在，9不存在，1表示有，0表示没有，那么mask由000到111就是枚举的所有

剑指 Offer II 080. 含有 k 个元素的组合

给定两个整数 n 和 k，返回 1 … n 中所有可能的 k 个数的组合。
输入: n = 4, k = 2
输出:
[
[2,4],
[3,4],
[2,3],
[1,2],
[1,3],
[1,4],
]

方法：递归

代码

class Solution {
private:
    void helper(int i, int n, int k, vector<vector<int>>& ret, vector<int>& cur) {
        if (cur.size() == k) {
            ret.emplace_back(cur);
            return;
        }
        // i 超界
        if (i > n) {
            return;
        }
        // 加入 i
        cur.push_back(i);
        helper(i + 1, n, k, ret, cur);
        cur.pop_back();
        //  不加入 i
        helper(i + 1, n, k, ret, cur);
    }

public:
    vector<vector<int>> combine(int n, int k) {
        vector<vector<int>> ret;
        vector<int> cur;
        helper(1, n, k, ret, cur);
        return ret;
    }
};

剑指 Offer II 081. 允许重复选择元素的组合

给定一个无重复元素的正整数数组 candidates 和一个正整数 target ，找出 candidates 中所有可以使数字和为目标数 target 的唯一组合。
candidates 中的数字可以无限制重复被选取。如果至少一个所选数字数量不同，则两种组合是不同的。
对于给定的输入，保证和为 target 的唯一组合数少于 150 个。

方法：当前元素加入或不加入递归+剪枝

这道题与之前的唯一区别就是同一个数字可以多次选择。这道题中每一步都从集合中取出一个元素时，存在多个选择，一种是不添加该数字，其他选择就是选择 1 次该数字，2 次该数字…。
其实归根到底，也是两种选择，一种是选择不添加，另一种是选择添加。如果选择不添加，那么只需要调用递归函数判断下一个数字。如果选择添加，那么只需要调用递归函数继续判断该数字。

代码

class Solution {
private:
    void helper(vector<int>& candidates, int target, int index, vector<vector<int>>& ret, vector<int>& cur) {
        // 得到答案
        if (target == 0) {
            ret.emplace_back(cur);
            return;
        }
        // 超界
        if (target < 0 || index == candidates.size()) {
            return;
        }
        // 加入 candidates[index]
        cur.push_back(candidates[index]);
        helper(candidates, target - candidates[index], index, ret, cur);
        cur.pop_back();
        // 不加入 candidates[index]
        helper(candidates, target, index + 1, ret, cur);
    }
public:
    vector<vector<int>> combinationSum(vector<int>& candidates, int target) {
        vector<vector<int>> ret;
        vector<int> cur;
        helper(candidates, target, 0, ret, cur);
        return ret;
    }
};

剑指 Offer II 082. 含有重复元素集合的组合

给定一个可能有重复数字的整数数组 candidates 和一个目标数 target ，找出 candidates 中所有可以使数字和为 target 的组合。

candidates 中的每个数字在每个组合中只能使用一次，解集不能包含重复的组合。

方法：在某一步决定跳过某个值为 m 的数字时，跳过所有值为 m 的数字

比如[2,2,2,4,2]，目标为6，可能会出,2，4和4，2重复的情况，因此应该需要先对数组进行排序
本题即使某步决定跳过该数字，之后也有可能会继续选择该数字。可以总结出避免重复的方法是，当在某一步决定跳过某个值为 m 的数字时，跳过所有值为 m 的数字。
先排序

class Solution {
private:
    // 跳过所有相同的数字
    inline int getNext(vector<int>& candidates, int index) {
        for (int i = index + 1; i < candidates.size(); ++i) {
            if (candidates[i] != candidates[index]) {
                return i;
            }
        }
        return candidates.size();
    }
    void helper(vector<int>& candidates, int index, int target, vector<vector<int>>& ret, vector<int>& cur) {
        if (target == 0) {
            ret.emplace_back(cur);
            return;
        }
        if (target < 0 || index == candidates.size()) {
            return;
        }
        // 加入 candidates[index]
        cur.push_back(candidates[index]);
        helper(candidates, index + 1, target - candidates[index], ret, cur);
        cur.pop_back();
        // 不加入 candidates[index]
        helper(candidates, getNext(candidates, index), target, ret, cur);
    }
public:
    vector<vector<int>> combinationSum2(vector<int>& candidates, int target) {
        vector<vector<int>> ret;
        vector<int> cur;
        sort(candidates.begin(), candidates.end());
        helper(candidates, 0, target, ret, cur);
        return ret;
    }
};

剑指 Offer II 083. 没有重复元素集合的全排列

给定一个不含重复数字的整数数组 nums ，返回其 所有可能的全排列 。可以 按任意顺序 返回答案。
输入：nums = [1,2,3]
输出：[[1,2,3],[1,3,2],[2,1,3],[2,3,1],[3,1,2],[3,2,1]]

方法一：深度遍历树，树的路径即排列

每次操作，从待选列表里拿出一个数，将其作为不变的头部，再将剩余待选值递归地产生全排列，最后将头部值插在前边。对每一级而言，此处的回溯操作在于，每次更换选择的头部值，将此前选择的头部值放进待选列表中，再做深度优先搜索。

剪枝是在向下判断当前节点是否已经加入，如果已经加入那么跳过

class Solution {
public:
    vector<vector<int>> permute(vector<int>& nums) {
        vector<vector<int>> res;
        vector<int> path;
        vector<bool> used = vector<bool>(nums.size());
        dfs(nums, path, res, used);
        return res;
    }

    void dfs(vector<int> nums,
        vector<int>& path,
        vector<vector<int>>& res,
        vector<bool>& used) {
        if (path.size() == nums.size()) {
            res.emplace_back(path);
            return;
        }

        for (int i = 0; i < nums.size(); i++) {
            if (used[i]) continue;
            path.push_back(nums[i]);
            used[i] = true;
            dfs(nums, path, res, used);
            path.pop_back();
            used[i] = false;
        }
    }
};

方法二：交换元素的位置

第一个位置，交换n个位置获得第一个位置的元素，将每次开辟一个分支

代码

class Solution {
public:
    void backtrack(vector<vector<int>>& res, vector<int>& output, int first, int len) {
        // 所有数都填完了
        if (first == len) {
            res.emplace_back(output);
            return;
        }
        for (int i = first; i < len; ++i) { 
            // 动态维护数组
            swap(output[i], output[first]);
            // 继续递归填下一个数
            backtrack(res, output, first + 1, len);
            // 撤销操作
            swap(output[i], output[first]);
        }
    }
    vector<vector<int>> permute(vector<int>& nums) {
        vector<vector<int> > res;
        backtrack(res, nums, 0, (int)nums.size());
        return res;
    }
};

剑指 Offer II 084. 含有重复元素集合的全排列

给定一个可包含重复数字的整数集合 nums ，按任意顺序 返回它所有不重复的全排列。
输入：nums = [1,1,2]
输出：
[[1,1,2],
[1,2,1],
[2,1,1]]

方法，先排序如果在一条路径里如果重复数字保证前面那个先访问

class Solution {
    vector<int> vis;

public:
    void backtrack(vector<int>& nums, vector<vector<int>>& ans, int idx, vector<int>& perm) {
        if (idx == nums.size()) {
            ans.emplace_back(perm);
            return;
        }
        for (int i = 0; i < (int)nums.size(); ++i) {
            if (vis[i] || (i > 0 && nums[i] == nums[i - 1] && !vis[i - 1])) {
                continue;
            }
            perm.emplace_back(nums[i]);
            vis[i] = 1;
            backtrack(nums, ans, idx + 1, perm);
            vis[i] = 0;
            perm.pop_back();
        }
    }

    vector<vector<int>> permuteUnique(vector<int>& nums) {
        vector<vector<int>> ans;
        vector<int> perm;
        vis.resize(nums.size());
        sort(nums.begin(), nums.end());
        backtrack(nums, ans, 0, perm);
        return ans;
    }
};

剑指 Offer II 085. 生成匹配的括号

正整数 n 代表生成括号的对数，请设计一个函数，用于能够生成所有可能的并且 有效的 括号组合。
输入：n = 3
输出：[“((()))”,“(()())”,“(())()”,“()(())”,“()()()”]
3个就是生成三个括号

方法一暴力递归，然后左括号减去右括号检查，只要值小于1或者结束不为0就是无效，就去掉

代码

class Solution {
    bool valid(const string& str) {
        int balance = 0;
        for (char c : str) {
            if (c == '(') {
                ++balance;
            }
            else {
                --balance;
            }
            if (balance < 0) {
                return false;
            }
        }
        return balance == 0;
    }

    void generate_all(string& current, int n, vector<string>& result) {
        if (n == current.size()) {
            if (valid(current)) {
                result.push_back(current);
            }
            return;
        }
        current += '(';
        generate_all(current, n, result);
        current.pop_back();
        current += ')';
        generate_all(current, n, result);
        current.pop_back();
    }
public:
    vector<string> generateParenthesis(int n) {
        vector<string> result;
        string current;
        generate_all(current, n * 2, result);
        return result;
    }
};

方法一的改进

在序列有效时，加入(或者),，具体看代码

代码

class Solution {
    void backtrack(vector<string>& ans, string& cur, int open, int close, int n) {
        if (cur.size() == n * 2) {
            ans.push_back(cur);
            return;
        }
        if (open < n) {
            cur.push_back('(');
            backtrack(ans, cur, open + 1, close, n);
            cur.pop_back();
        }
        if (close < open) {
            cur.push_back(')');
            backtrack(ans, cur, open, close + 1, n);
            cur.pop_back();
        }
    }
public:
    vector<string> generateParenthesis(int n) {
        vector<string> result;
        string current;
        backtrack(result, current, 0, 0, n);
        return result;
    }
};

前面的一些总结

每一步面临两个选项，要么加入，要么不加入。或者要么加这一个，要么加另一个，那么就适合回溯法。
执行每个选项都会生成一个分支。但是执行每一个选项都要消除影响

解决该问题需要若干步，每一步又面临若干个选择，最后需要返回所有符合要求的结果，所以本题可以用回溯法解决

剑指 Offer II 086. 分割回文子字符串

给定一个字符串 s ，请将 s 分割成一些子串，使每个子串都是 回文串 ，返回 s 所有可能的分割方案。

回文串 是正着读和反着读都一样的字符串。

输入：s = “google”
输出：[[“g”,“o”,“o”,“g”,“l”,“e”],[“g”,“oo”,“g”,“l”,“e”],[“goog”,“l”,“e”]]

回溯，如果当前字符后还有n个字符，那么它还有n种选择

那样也就是经典的回溯，用for循环遍历这n种选择

代码

class Solution {
private:
    // 回溯
    void helper(string& s, int index, vector<vector<string>>& ret, vector<string>& cur) {
        if (index == s.size()) {
            ret.emplace_back(cur);
            return;
        }

        for (int i = index; i < s.size(); ++i) {
            if (isPalindrom(s, index, i)) {
                string str = s.substr(index, i - index + 1);
                cur.push_back(str);
                helper(s, i + 1, ret, cur);
                cur.pop_back();
            }
        }
    }

    // 回文判断
    bool isPalindrom(string& s, int left, int right) {
        while (left < right) {
            if (s[left++] != s[right--]) {
                return false;
            }
        }
        return true;
    }

public:
    vector<vector<string>> partition(string s) {
        vector<vector<string>> ret;
        vector<string> cur;
        helper(s, 0, ret, cur);
        return ret;
    }
};

剑指 Offer II 087. 复原 IP

给定一个只包含数字的字符串 s ，用以表示一个 IP 地址，返回所有可能从 s 获得的 有效 IP 地址 。你可以按任何顺序返回答案。

有效 IP 地址 正好由四个整数（每个整数位于 0 到 255 之间组成，且不能含有前导 0），整数之间用 ‘.’ 分隔。

例如：“0.1.2.201” 和 “192.168.1.1” 是 有效 IP 地址，但是 “0.011.255.245”、“192.168.1.312” 和 “192.168@1.1” 是 无效 IP 地址。

输入：s = “25525511135”
输出：[“255.255.11.135”,“255.255.111.35”]

回溯

代码

class Solution {
private:
    static constexpr int SEG_COUNT = 4;

private:
    vector<string> ans;
    vector<int> segments;

public:
    //segId表示ip地址的第几段，∈[0,3]
    //segStart表示从字符串的什么位置开始的
    void dfs(const string& s, int segId, int segStart) {
        // 如果找到了 4 段 IP 地址并且遍历完了字符串，那么就是一种答案
        if (segId == SEG_COUNT) {//segId==SEG_COUNT，由于segId是从0开始的，所以这里就超了
            if (segStart == s.size()) {//如果开始的位置变为字符串的终止位置
                string ipAddr;
                for (int i = 0; i < SEG_COUNT; ++i) {
                    ipAddr += to_string(segments[i]);
                    if (i != SEG_COUNT - 1) {
                        ipAddr += ".";
                    }
                }
                ans.push_back(move(ipAddr));
            }
            return;
        }

        // 如果还没有找到 4 段 IP 地址就已经遍历完了字符串，那么提前回溯
        if (segStart == s.size()) {
            return;
        }

        // 由于不能有前导零，如果当前数字为 0，那么这一段 IP 地址只能为 0
        if (s[segStart] == '0') {
            segments[segId] = 0;
            dfs(s, segId + 1, segStart + 1);
        }

        // 一般情况，枚举每一种可能性并递归
        int addr = 0;
        for (int segEnd = segStart; segEnd < s.size(); ++segEnd) {
            addr = addr * 10 + (s[segEnd] - '0');
            if (addr > 0 && addr <= 0xFF) {  //0xFF换成十进制为255
                segments[segId] = addr;
                dfs(s, segId + 1, segEnd + 1);
            }
            else {//如果大于255，那么跳出for循环
                break;
            }
        }
    }

    vector<string> restoreIpAddresses(string s) {
        segments.resize(SEG_COUNT);//容器重新设置大小
        dfs(s, 0, 0);
        return ans;
    }
};