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

  • A+
所属分类:LeetCode

剑指 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,那么就将结果加入到容器中
剑指offer79-87二进制枚举、回溯
如果加入和不加入反过来,也要将加入的元素删除掉
剑指offer79-87二进制枚举、回溯

方法二:二进制枚举

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

剑指 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],
]

方法:递归

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

代码

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 次该数字…。
其实归根到底,也是两种选择,一种是选择不添加,另一种是选择添加。如果选择不添加,那么只需要调用递归函数判断下一个数字。如果选择添加,那么只需要调用递归函数继续判断该数字
剑指offer79-87二进制枚举、回溯

代码

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 的数字。
先排序
剑指offer79-87二进制枚举、回溯
剑指offer79-87二进制枚举、回溯

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

方法一:深度遍历树,树的路径即排列

每次操作,从待选列表里拿出一个数,将其作为不变的头部,再将剩余待选值递归地产生全排列,最后将头部值插在前边。对每一级而言,此处的回溯操作在于,每次更换选择的头部值,将此前选择的头部值放进待选列表中,再做深度优先搜索。
剑指offer79-87二进制枚举、回溯
剪枝是在向下判断当前节点是否已经加入,如果已经加入那么跳过
剑指offer79-87二进制枚举、回溯

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个位置获得第一个位置的元素,将每次开辟一个分支
剑指offer79-87二进制枚举、回溯

代码

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

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

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

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就是无效,就去掉

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

代码

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;
    }
};

方法一的改进

在序列有效时,加入(或者),,具体看代码
剑指offer79-87二进制枚举、回溯

代码

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种选择
剑指offer79-87二进制枚举、回溯
剑指offer79-87二进制枚举、回溯

代码

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

回溯

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

代码

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;
    }
};
w3cjava

发表评论

:?: :razz: :sad: :evil: :!: :smile: :oops: :grin: :eek: :shock: :???: :cool: :lol: :mad: :twisted: :roll: :wink: :idea: :arrow: :neutral: :cry: :mrgreen: