Backtracking

52. N Queens II 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."], [".

51. N Queens 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...", ".

47. PermutationsII 全排列2

Given a collection of numbers that might contain duplicates, return all possible unique permutations. Example: Input: [1,1,2] Output: [ [1,1,2], [1,2,1], [2,1,1] ] 跟上道题不一样的地方就是会有重复的数字 vector<vector<int>> permuteUnique(vector<int>& nums) { // 这里用set来去重,因为递归回退的时候可能会有重复的元素 set<vector<int>> res{}; if (nums.size()==0) return vector<vector<int>>(); sort(nums.begin(), nums.end()); permuteUniqueCore(res, nums, 0, nums.size()); return vector<vector<int>> (res.begin(),res.end()); } void permuteUniqueCore(set<vector<int>> &res,vector<int> &nums,int k,int n){ if (k == n) { printArr(nums); res.insert(nums); return; } for (int i = k; i<n; i++) { if (nums[k]==nums[i] && i!

46 Permutations 全排列

Given a collection of distinct(不同) integers, return all possible permutations(全排列). Example: Input: [1,2,3] Output: [ [1,2,3], [1,3,2], [2,1,3], [2,3,1], [3,1,2], [3,2,1] ] 这道题跟这道题https://github.com/longpf/AtOffer#27-字符串的排列简直一模一样 vector<vector<int>> permute(vector<int>& nums) { vector<vector<int>> res{}; if (nums.size() == 0) return res; permuteCore(res, nums, 0, nums.size()); return res; } void permuteCore(vector<vector<int>> &res,vector<int> &num,int k,int n){ if (k == n) { res.push_back(num); return; } for (int i = k; i<n; i++) { swap(num[i], num[k]); permuteCore(res, num, k+1, n); swap(num[i], num[k]); } }

44. Wildcard Matching 通配符匹配

Given an input string (s) and a pattern (p), implement wildcard pattern matching with support for '?' and '*'. '?' Matches any single character. '*' Matches any sequence of characters (including the empty sequence). The matching should cover the entire input string (not partial). Note: s could be empty and contains only lowercase letters a-z. p could be empty and contains only lowercase letters a-z, and characters like ?

40. Combination Sum II 组合之和之二

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:

39. Combination Sum 组合之和

Given a set of candidate numbers (candidates) (without duplicates) and a target number (target), find all unique combinations in candidates where the candidate numbers sums to target. The same repeated number may be chosen from candidates unlimited number of times. Note: All numbers (including target) will be positive integers. The solution set must not contain duplicate combinations. Example 1: Input: candidates = [2,3,6,7], target = 7, A solution set is: [ [7], [2,2,3] ] Example 2:

37. Sudoku Solver 求数独的一个解

Write a program to solve a Sudoku puzzle by filling the empty cells. A sudoku solution must satisfy all of the following rules: Each of the digits 1-9 must occur exactly once in each row. Each of the digits 1-9 must occur exactly once in each column. Each of the the digits 1-9 must occur exactly once in each of the 9 3x3 sub-boxes of the grid. Empty cells are indicated by the character ‘.

22. Generate Parentheses 生成括号

Given n pairs of parentheses, write a function to generate all combinations of well-formed parentheses. For example, given n = 3, a solution set is: [ "((()))", "(()())", "(())()", "()(())", "()()()" ] Difficulty: Medium 这道题让我们列举出所有的括号字符串,前面还有一题20. Valid Parentheses 验证括号也是关于括号的.这里让列举出所有可能,可以优先考虑递归和DFS.定义left,right分别表示剩余左括号的数量和剩余的右括号的数量.如果在某次的递归中,left>right说明在已经生成的字符串中右括号的数量大于左括号的数量,是不合理的.当left,right都为0的时候,说明已经生成一个可用的括号串.其实这里有DFS的思想.为什么呢.看看下面是怎样递归的顺序,以题目给的例子n=3. ( (( ((( ((() ((()) ((())) (()()) ~ ()()() DFS(深度优先),这里可以想象成左括号优先 解法1 就是上面分析的解法 class Solution { public: vector<string> generateParenthesis(int n) { vector<string> res; generateParenthesisDFS(n,n,"",res); return res; } void generateParenthesisDFS(int left,int right,string out,vector<string>& res) { if (left>right) return; if (left==0 && right==0) res.

17. Letter Combinations of a Phone Number 电话号码的字母组合

Given a digit string, 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. Input: Digit string "23" Output: ["ad", "ae", "af", "bd", "be", "bf", "cd", "ce", "cf"]. Note: Although the above answer is in lexicographical order, your answer could be in any order you want. 这道题让我们求电话号码的字母组合, 既2~9中,每个数字都代表2到3个字母,然后给出一个数字的字符串,求出这串数字可能代表的所有字母串.这道题可以用DFS的思想解决,关于DFS可以看二叉树 深度优先搜索（DFS）、广度优先搜索（BFS）,可以简单的了解一下.那为什么说是DFS思想呢,比如给出”2345”,那个对应的结果为adgj,adgk,adgl,adhj,adhk,adhl...cfil这个顺序可以看做DFS的思想.大概这个意思. 解法1 解法1就是上面的分析的解法. class Solution { public: vector<string> letterCombinations(string digits) { vector<string> res; if (digits.

10. Regular Expression Matching 正则表达式匹配

Implement regular expression matching with support for '.' and '*'. '.' Matches any single character. '*' Matches zero or more of the preceding element. The matching should cover the entire input string (not partial). The function prototype should be: bool isMatch(const char *s, const char *p) Some examples: isMatch("aa","a") → false isMatch("aa","aa") → true isMatch("aaa","aa") → false isMatch("aa", "a*") → true isMatch("aa", ".*") → true isMatch("ab", ".*") → true isMatch("aab", "c*a*b") → true Difficulty: Hard