递归、回溯和分治

问题1 求子集

1-a 求子集

Given a set of distinct integers, nums, return all possible subsets (the power set).

Note: The solution set must not contain duplicate subsets.

Example:

Input: nums = [1,2,3] Output: [ [3], [1], [2], [1,2,3], [1,3], [2,3], [1,2], [] ]

链接：https://leetcode-cn.com/problems/subsets/

求一组数可以组成的所有子集。

方法一 回溯法

#include <vector> class Solution { public: vector<vector<int>> subsets(vector<int> &nums) { vector<vector<int>> result; vector<int> item; result.push_back(item); // 将空集 push 到 result 中 generate(0, nums, item, result); // 计算各个子集 return result; } private: void generate(int i, vector<int> &nums, vector<int> &item, vector<vector<int>> &result) { if (i >= nums.size()) { return; } item.push_back(nums[i]); result.push_back(item); // 将当前生成的子集添加进 result generate(i + 1, nums, item, result); // 包含本元素的子集 item.pop_back(); generate(i + 1, nums, item, result); // 不包含本元素的子集 } }

让generate负责：

生成以当前数字结尾的列表生成以后面数字结尾的，包含本数字和不包含本数字的，所有列表

方法二 位运算

vector<vector<int> subsets(vector<int> nums) { vector<vector<int>> result; int all_set = 1 << nums.size(); // 2^nums.size() for (int i = 0; i < all_set; i++) { vector<int> item; for (int j = 0; j < nums.size(); j++) { if (i & (1 << j)) { // (i >> j) & 1 item.push_back(nums[j]); } } result.push_back(item); } return result; }

1-b 求有重复元素的子集

Given a collection of integers that might contain duplicates, *nums*, return all possible subsets (the power set).

Note: The solution set must not contain duplicate subsets.

Example:

Input: [1,2,2] Output: [ [2], [1], [1,2,2], [2,2], [1,2], [] ]

链接：https://leetcode-cn.com/problems/subsets-ii/

方法一 用set过滤重复子集

跟1-a的方法一一样只不过不是把item push到(vector)result中而是result set中。

方法二 一轮选一个

之前的思路思路都是一次递归决定一个数字是否要选，这个思路是每一次递归都要选一个数字。

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

1-c 组合数之和

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

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

Note:

All numbers (including target) will be positive integers.The solution set must not contain duplicate combinations.

Example 1:

Input: candidates = [10,1,2,7,6,1,5], target = 8, A solution set is: [ [1, 7], [1, 2, 5], [2, 6], [1, 1, 6] ]

Example 2:

Input: candidates = [2,5,2,1,2], target = 5, A solution set is: [ [1,2,2], [5] ]

链接：https://leetcode-cn.com/problems/combination-sum-ii/

求一组数的所有子集中和为k的子集。

问题2 生成括号

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

Example 1:

Input: n = 3 Output: ["((()))","(()())","(())()","()(())","()()()"]

Example 2:

Input: n = 1 Output: ["()"]

Constraints:

1 <= n <= 8

链接：https://leetcode-cn.com/problems/generate-parentheses/

class Solution { public: vector<string> generateParenthesis(int n) { vector<string> result; generate("", n, n, result); return result; } private: void generate(string item, int left, int right, vector<string> &result) { if (left == 0 && right == 0) { result.push_back(item); return; } if (left > 0) { generate(item + '(', left - 1, right, result); } if (right > left) { generate(item + ')', left, right - 1, result); } } };

让generate负责生成以item + (或item + )开头的括号。

这种方法递归的深度比较深，速度慢。

问题3 N皇后问题

The n-queens puzzle is the problem of placing n queens on an n×n chessboard such that no two queens attack each other.

Given an integer n, return all distinct solutions to the n-queens puzzle.

Each solution contains a distinct board configuration of the n-queens’ placement, where 'Q' and '.' both indicate a queen and an empty space respectively.

Example:

Input: 4 Output: [ [".Q..", // Solution 1 "...Q", "Q...", "..Q."], ["..Q.", // Solution 2 "Q...", "...Q", ".Q.."] ] Explanation: There exist two distinct solutions to the 4-queens puzzle as shown above.

链接：https://leetcode-cn.com/problems/n-queens/

将N个皇后摆放在N×N的棋盘中，每个皇后可以攻击同一行同一列和斜对角方向。

皇后是国际象棋中最厉害的棋子。

方向数组： 定义方向数组 [(-1,0),(1,0),(0,-1),(0,1),(-1,-1)……]

问题4 逆序数

You are given an integer array nums and you have to return a new counts array. The counts array has the property where counts[i] is the number of smaller elements to the right of nums[i].

Example 1:

Input: nums = [5,2,6,1] Output: [2,1,1,0] Explanation: To the right of 5 there are 2 smaller elements (2 and 1). To the right of 2 there is only 1 smaller element (1). To the right of 6 there is 1 smaller element (1). To the right of 1 there is 0 smaller element.

Constraints:

0 <= nums.length <= 10^5-10^4 <= nums[i] <= 10^4

链接：https://leetcode-cn.com/problems/count-of-smaller-numbers-after-self/

求nums[i]右侧比nums[i]小的数。

在归并过程中，如果 i j 两个指针指向的数中先放 j，表示右边的数(j及以前的数)与左边的数(i及以后的数)有交换，那就表示右边的数比左边的数小。

只能在归并排序的过程中进行？不是的，任何排序算法都行，比如冒泡排序。只不过归并排序属于复杂度比较低的好写的算法。

不过leetcode官方提供的方式是「离散化树状数组」，需要学一下。