LeetCode + 《剑指Offer II》刷题笔记。

回溯法

用回溯法解决问题的过程可以形象地用一个树形结构表示，求解问题的每个步骤可以看作树中的一个节点。如果在某一步有n个可能的选项，每个选项是树中的一条边，经过这些边就可以到达该节点的n个子节点。

采用回溯法解决问题的过程实质上是在树形结构中从根节点开始进行深度优先遍历。通常，回溯法的深度优先遍历用递归代码实现。

组合和排列

从一个包含m个元素的集合中挑选出n个元素（0≤n≤m）形成一个子集。一个子集又可以称为一个组合。如果两个子集（组合）的元素完全相同只是顺序不同，那么它们可以看作同一个子集（组合）。

从一个包含m个元素的集合中挑选出n个元素（0≤n≤m）并按照某种顺序形成一个排列。m等于n的排列又称为全排列。如果两个排列的元素完全相同只是顺序不同，那么它们就是两个不同的排列。

组合与元素的顺序无关，排列与元素的顺序相关。

例如，从数据集合[1，2，3]中选出两个数字能形成3个组合，分别是[1，2]、[1，3]和[2，3]；但从数据集合[1，2，3]中选出两个数字能形成6个排列，分别是[1，2]、[2，1]、[1，3]、[3，1]、[2，3]和[3，2]。

079. 所有子集

剑指 Offer II 079. 所有子集

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21


class Solution {
public:
    vector<int> t;
    vector<vector<int>> res;
    void dfs(int cur,vector<int>& nums){
        if(cur==nums.size()){
            res.push_back(t);
            return;
        }
        // 考虑选择当前位置
        t.push_back(nums[cur]);
        dfs(cur+1,nums);
        t.pop_back();
        // 考虑不选择当前位置
        dfs(cur+1,nums);
    }
    vector<vector<int>> subsets(vector<int>& nums) {
        dfs(0,nums);
        return res;
    }
};

使用ArrayList,移除最后一个元素:temp.remove(temp.size()-1);

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18


class Solution {
    private List<Integer> temp=new ArrayList<>();
    private List<List<Integer>> res=new ArrayList<List<Integer>>();
    public List<List<Integer>> subsets(int[] nums) {
        dfs(nums,0);
        return res;
    }
    private void dfs(int[] nums,int index){
        if(index==nums.length){
            res.add(new ArrayList<Integer>(temp));
            return;
        }
        temp.add(nums[index]);
        dfs(nums,index+1);
        temp.remove(temp.size()-1);
        dfs(nums,index+1);
    }
}

使用LinkedList,移除最后一个元素:temp.removeLast();

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18


class Solution {
    private LinkedList<Integer> temp=new LinkedList<>();
    private List<List<Integer>> res=new LinkedList<>();
    public List<List<Integer>> subsets(int[] nums) {
        dfs(nums,0);
        return res;
    }
    private void dfs(int[] nums,int index){
        if(index==nums.length){
            res.add(new LinkedList<Integer>(temp));
            return;
        }
        temp.add(nums[index]);
        dfs(nums,index+1);
        temp.removeLast();
        dfs(nums,index+1);
    }
}

时间复杂度：O(n*2^n)，由于每个元素都有2个选项，一共 2^n个状态，每种状态需要 O(n) 的时间来构造子集。

空间复杂度：O(n)，临时数组 t 的空间代价是 O(n)，递归时栈空间的代价为 O(n)。

080. 含有 k 个元素的组合

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

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21


class Solution {
public:
    vector<int> temp;
    vector<vector<int>> res;
    void dfs(int cur,int n,int k){
        // 剪枝：temp长度加上区间[cur,n]的长度小于k，不可能构造出长度为k的temp
        if(temp.size()+(n-cur+1)<k) return;
        if(temp.size()==k){
            res.push_back(temp);
            return;
        }
        temp.push_back(cur);
        dfs(cur+1,n,k);
        temp.pop_back();
        dfs(cur+1,n,k);
    }
    vector<vector<int>> combine(int n, int k) {
        dfs(1,n,k);
        return res;
    }
};

39. Combination Sum

LeetCode 39 - Combination Sum

candidates 中的数字可以无限制重复被选取。如果至少一个所选数字数量不同，则两种组合是不同的。

每一步都从集合中取出一个下标为i的数字，此时面临两个选择。

跳过这个数字不将该数字添加到组合中，那么这一步实际上什么都不做，接下来处理下标为i+1的数字。
将数字添加到组合中，由于一个数字可以重复在组合中出现，也就是说，下一步可能再次选择同一个数字，因此下一步仍然处理下标为i的数字

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27


class Solution {
public:
    vector<int> temp;
    vector<vector<int>> res;
    void dfs(vector<int>& candidates,int target,int cur){
        if(cur==candidates.size()){
            return;
        }
        if(target==0){
            res.push_back(temp);
            return;
        }
        // 直接跳过
        dfs(candidates,target,cur+1);
        // 选择当前数 
        if(target-candidates[cur]>=0){
            temp.push_back(candidates[cur]);
            // 下标依然是cur
            dfs(candidates,target-candidates[cur],cur);
            temp.pop_back();
        }
    }
    vector<vector<int>> combinationSum(vector<int>& candidates, int target) {
        dfs(candidates,target,0);
        return res;
    }
};

上述代码中的target是组合combination中元素之和的目标值。每当在组合中添加一个数字时，就从target中减去这个数字。当target等于0时，组合中的所有元素之和正好等于target，因此也就找到了一个符合条件的组合。

时间复杂度：O(S)，其中 S 为所有可行解的长度之和。O(n*2^n) 是一个比较松的上界。
空间复杂度：O(target)

40 Combination Sum II

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28


class Solution {
private:
    vector<int> temp;
    vector<vector<int>> res;
public:
    vector<vector<int>> combinationSum2(vector<int>& candidates, int target) {
        sort(candidates.begin(),candidates.end());
        dfs(candidates,target,0);
        return res;
    }
    void dfs(vector<int>& candidates,int target,int cur){
        if(target==0){
            res.push_back(temp);
            return;
        }
        if(cur==candidates.size()) return;
        if(target-candidates[cur]>=0){
            temp.push_back(candidates[cur]);
            dfs(candidates,target-candidates[cur],cur+1);
            temp.pop_back();
            int next=cur;
            while(next<candidates.size() && candidates[next]==candidates[cur]){
                next++;
            }
            dfs(candidates,target,next);
        }
    }
};

082. 含有重复元素集合的组合

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

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

输入的集合中有重复的数字但输出不得包含重复的组合。如果输入的集合中有重复的数字，不经过特殊处理将产生重复的组合。例如，从集合[2，2，2]中选出2个数字本来能组成3个组合，但3个组合都是[2，2]，因此它们是重复的组合，在本题中只能算1个。另外，组合不考虑数字的顺序，如组合[2，2，4]、[2，4，2]和[4，2，2]只能算一个组合。

避免重复的组合的方法是当在某一步决定跳过某个值为m的数字时，跳过所有值为m的数字。

例如，假设求[2，2，2]的组合，如果在处理第1个2时决定跳过它并跳过所有的2，那么得到的是一个空的组合。如果选择第1个2之后决定跳过第2个2并连带跳过后面的2，那么得到的是组合[2]。如果选择前两个2之后决定跳过第3个2，那么得到的是组合[2，2]。如果3个2都被选择，则得到组合[2，2，2]。采用这个办法就可以避免产生重复的组合，如避免了两种产生重复组合[2，2]的情形，一种情形是跳过第1个2选择后面两个2，另一种情形是跳过中间一个2选择前后两个2。

为了方便跳过后面所有值相同的数字，可以将集合中的所有数字排序，把相同的数字放在一起，这样方便比较数字。当决定跳过某个值的数字时，可以按顺序扫描后面的数字，直到找到不同的值为止。

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23


class Solution {
    LinkedList<Integer> combination=new LinkedList<>();
    List<List<Integer>> result=new LinkedList<>();
    void dfs(int[] candidates,int target,int index){
        if(target==0){
            // 注意这里是new LinkedList<>(combination)，不能直接写combination
            result.add(new LinkedList<>(combination));
        }else if(target>0 && index<candidates.length){
            int next=index;
            while(next<candidates.length && candidates[next]==candidates[index]) next++;
            dfs(candidates,target,next);
          
            combination.addLast(candidates[index]);
            dfs(candidates,target-candidates[index],index+1);
            combination.removeLast();
        }
    }
    public List<List<Integer>> combinationSum2(int[] candidates, int target) {
        Arrays.sort(candidates);
        dfs(candidates,target,0);
        return result;
    }
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25


class Solution {
    List<List<Integer>> result=new LinkedList<>();
    LinkedList<Integer> combination=new LinkedList<>();
    void dfs(int[] candidates,int target,int index){
        if(target==0){
            // 注意这里是new LinkedList<>(combination)，不能直接写combination
            result.add(new LinkedList<>(combination));
        }
      	// 注意这里if(index==candidates.length) return;的位置，应该放在这里。
        if(index==candidates.length) return;
        if(target-candidates[index]>=0){
            int next=index;
            while(next<candidates.length && candidates[next]==candidates[index]) next++;
            dfs(candidates,target,next);
            combination.addLast(candidates[index]);
            dfs(candidates,target-candidates[index],index+1);
            combination.removeLast();
        }
    }
    public List<List<Integer>> combinationSum2(int[] candidates, int target) {
        Arrays.sort(candidates);
        dfs(candidates,target,0);
        return result;
    }
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30


class Solution {
public:
    vector<int> temp;
    vector<vector<int>> res;
    void dfs(vector<int>& candidates,int target,int cur){
        if(target==0){
            res.push_back(temp);
            return;
        }
        if(cur==candidates.size()){
            return;
        }
        if(target-candidates[cur]>=0){
            // 当在某一步决定跳过某个值为m的数字时，跳过所有值为m的数字
            int next=cur;
            while(next<candidates.size() && candidates[next]==candidates[cur]){
                next++;
            }
            dfs(candidates,target,next);
            temp.push_back(candidates[cur]);
            dfs(candidates,target-candidates[cur],cur+1);
            temp.pop_back();
        }
    }
    vector<vector<int>> combinationSum2(vector<int>& candidates, int target) {
        sort(candidates.begin(),candidates.end());
        dfs(candidates,target,0);
        return res;
    }
};

083. 没有重复元素集合的全排列

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

如果输入的集合中有n个元素，那么生成一个全排列需要n步。当生成排列的第1个数字时会面临n个选项，即n个数字都有可能成为排列的第1个数字。生成排列的第1个数字之后接下来生成第2个数字，此时面临n-1个选项，即剩下的n-1个数字都有可能成为第2个数字。然后以此类推，直到生成最后一个数字，此时只剩下1个数字，也就只有1个选项。

解决这个问题可以分成n步，而且每一步都面临若干选项，这是典型的适用回溯法的场景。

当函数backtrack生成排列的下标为i的数字时，下标从0到i-1的数字都已经选定，但数组nums中下标从i到n-1的数字（假设数组的长度为n）都有可能放到排列的下标为i的位置，因此函数backtrack中有一个for循环逐一用下标为i的数字交换它后面的数字。这个for循环包含下标为i的数字本身，这是因为它自己也能放在排列下标为i的位置。交换之后接着调用递归函数生成排列中下标为i+1的数字。由于之前已经交换了数组中的两个数字，修改了排列的状态，在函数退出之前需要清除对排列状态的修改，因此再次交换之前交换的两个数字。

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20


class Solution {
private:
    vector<vector<int>> res;
public:
    vector<vector<int>> permute(vector<int>& nums) {
        dfs(nums,0);
        return res;
    }
    void dfs(vector<int>& nums,int cur){
        if(cur==nums.size()){
            res.push_back(nums);
            return;
        }
        for(int j=cur;j<nums.size();j++){
            swap(nums[cur],nums[j]);
            dfs(nums,cur+1);
            swap(nums[cur],nums[j]);
        }
    }
};

假设数组nums的长度为n，当i等于0时递归函数helper中的for循环执行n次，当i等于1时for循环执行n-1次，以此类推，当i等于n-1时，for循环执行1次。因此，全排列的时间复杂度是O（n！）。

084. 含有重复元素集合的全排列

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

当处理到全排列的第i个数字时，如果已经将某个值为m的数字交换为排列的第i个数字，那么再遇到其他值为m的数字就跳过。

例如，输入nums为[2，1，1]并且处理排列中下标为0的数字时，将第1个数字1和数字2交换之后，就没有必要再将第2个数字1和数字2交换。在将第1个数字1和数字2交换之后，得到[1，2，1]，接着处理排列的第2个数字和第3个数字，这样就能生成两个排列，即[1，2，1]和[1，1，2]。

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26


class Solution {
private:
    vector<vector<int>> res;
public:
    vector<vector<int>> permuteUnique(vector<int>& nums) {
        sort(nums.begin(),nums.end());
        dfs(nums,0);
        return res;
    }
    void dfs(vector<int>& nums,int index){
        if(index==nums.size()){
            res.push_back(nums);
            return;
        }
        set<int> s;
        for(int j=index;j<nums.size();j++){
            //没找到 如果找到即为重复数字———>跳过
            if(s.find(nums[j])==s.end()){
                s.insert(nums[j]);
                swap(nums[j],nums[index]);
                dfs(nums,index+1);
                swap(nums[j],nums[index]);
            }
        }
    }
};

递归函数backtrack中使用了一个set，用来保存已经交换到排列下标为i的位置的所有值。只有当一个数值之前没有被交换到第i位时才做交换，否则直接跳过。

17 Letter Combinations of a Phone Number

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35


class Solution {
public:
    vector<string> res;
    unordered_map<char, string> phoneMap{
            {'2', "abc"},
            {'3', "def"},
            {'4', "ghi"},
            {'5', "jkl"},
            {'6', "mno"},
            {'7', "pqrs"},
            {'8', "tuv"},
            {'9', "wxyz"}
    };
    vector<string> letterCombinations(string digits) {
        if(digits.empty()) return res;
        string combination;
        backtrack(combination,digits,0);
        return res;
    }
    void backtrack(string& combination,string digits,int index){
        if(index==digits.length()){
            res.push_back(combination);
            return;
        }else{
            char digit=digits[index];
            string letters=phoneMap[digit];
            for(char letter:letters){
                combination.push_back(letter);
                backtrack(combination,digits,index+1);
                combination.pop_back();
            }
        }
        
    }
};

时间复杂度：O(3^m*4^n)
空间复杂度：O(m+n)

22 Generate Parentheses

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25


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

131 Palindrome Partitioning

backtrack

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32


class Solution {
public:
    vector<vector<string>> partition(string s) {
        vector<vector<string>> res;
        vector<string> temp;
        dfs(res,temp,s,0);
        return res;
    }
    void dfs(vector<vector<string>>& res,vector<string>& temp,string& s,int start){
        if(start==s.size()){
            res.push_back(temp);
            return;
        }
        for(int i=start;i<s.size();i++){
            if(isPalindrome(s,start,i)){
                temp.push_back(s.substr(start,i-start+1));
                dfs(res,temp,s,i+1);
                temp.pop_back();
            }
        }
    }
    bool isPalindrome(string& s,int left,int right){
        while(left<right){
            if(s[left]!=s[right]){
                return false;
            }
            left++;
            right--;
        }
        return true;
    }
};

时间复杂度：O(2^n)
空间复杂度：O(n)

DP+backtrack

时间复杂度：O(n*2^n)
空间复杂度：O(n*2^n)

推荐 NeetCode 的视频，虽然是用Python写的代码，但是前面的图解和讲解帮助很大。

40. Combination Sum II

Combination Sum II - Backtracking - Leetcode 40 - Python

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28


class Solution {
private:
    vector<int> temp;
    vector<vector<int>> res;
public:
    vector<vector<int>> combinationSum2(vector<int>& candidates, int target) {
        sort(candidates.begin(),candidates.end());
        dfs(candidates,target,0);
        return res;
    }
    void dfs(vector<int>& candidates,int target,int cur){
        if(target==0){
            res.push_back(temp);
            return;
        }
        if(cur==candidates.size()) return;
        if(target-candidates[cur]>=0){
            temp.push_back(candidates[cur]);
            dfs(candidates,target-candidates[cur],cur+1);
            temp.pop_back();
            int next=cur;
            while(next<candidates.size() && candidates[next]==candidates[cur]){
                next++;
            }
            dfs(candidates,target,next);
        }
    }
};

78. Subsets

1239 Maximum Length of a Concatenated String with Unique Characters

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34


class Solution {
public:
    int maxLength(vector<string> &arr) {
        vector<int> masks;
        for (string &s : arr) {
            int mask = 0;
            for (char ch : s) {
                ch -= 'a';
                if ((mask >> ch) & 1) { // 若 mask 已有 ch，则说明 s 含有重复字母，无法构成可行解
                    mask = 0;
                    break;
                }
                mask |= 1 << ch; // 将 ch 加入 mask 中
            }
            if (mask > 0) {
                masks.push_back(mask);
            }
        }

        int ans = 0;
        function<void(int, int)> backtrack = [&](int pos, int mask) {
            if (pos == masks.size()) {
                ans = max(ans, __builtin_popcount(mask));
                return;
            }
            if ((mask & masks[pos]) == 0) { // mask 和 masks[pos] 无公共元素
                backtrack(pos + 1, mask | masks[pos]);
            }
            backtrack(pos + 1, mask);
        };
        backtrack(0, 0);
        return ans;
    }
};

时间复杂度：O(∣Σ∣+2^n)。其中 ∣Σ∣ 是 arr 中所有字符串的长度之和。
空间复杂度：O(n)

Table of Contents

回溯法