46.全排列
给定一个不含重复数字的数组 nums ，返回其 所有可能的全排列 。你可以 按任意顺序 返回答案。
示例 1：输入：nums = [1,2,3] 输出：[[1,2,3],[1,3,2],[2,1,3],[2,3,1],[3,1,2],[3,2,1]]
示例 2：输入：nums = [0,1] 输出：[[0,1],[1,0]]
示例 3：输入：nums = [1] 输出：[[1]]
分析:
1.因为数组中的元素已经不重复, 我们 dfs + 回溯依次放入相应的元素, 直到判断元素个数已经达到目标元素个数
2.每次放入的时候判断重复的元素不能放入
class Solution {
public:
void dfs(vector<int>& nums, vector<int>& cur, vector<vector<int>>& ans) {
if (cur.size() == nums.size()) {
ans.push_back(cur);
return;
}
for (int i = 0; i < nums.size(); ++i) {
// 检测到数组中已经存在该元素不执行放入
if (find(cur.begin(), cur.end(), nums[i]) != cur.end()) {
continue;
}
cur.push_back(nums[i]);
dfs(nums, cur, ans);
cur.pop_back();
}
return;
}
vector<vector<int>> permute(vector<int>& nums) {
vector<vector<int>> ans;
vector<int> cur;
dfs(nums, cur, ans);
return ans;
}
};
47.全排列II
给定一个可包含重复数字的序列 nums ，按任意顺序 返回所有不重复的全排列。
示例 1：输入：nums = [1,1,2]
输出：
[
[1,1,2],
[1,2,1],
[2,1,1]
]示例 2：输入：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>> permuteUnique(vector<int>& nums) {
}
};
78.子集
给你一个整数数组 nums ，数组中的元素 互不相同 。返回该数组所有可能的子集（幂集）。解集 不能 包含重复的子集。你可以按 任意顺序 返回解集。
示例 1：输入：nums = [1,2,3] 输出：[[],[1],[2],[1,2],[3],[1,3],[2,3],[1,2,3]]
示例 2：输入：nums = [0] 输出：[[],[0]]
分析:
1.采用 dfs+回溯 的方式, 回溯完之后, 可以不选元素加入且继续路径向前+1 进行 dfs
class Solution {
public:
void dfs(int pos, vector<vector<int>>& ans, vector<int>& cur, vector<int>& nums) {
if (pos == nums.size()) {
ans.push_back(cur);
return;
}
cur.push_back(nums[pos]);
dfs(pos+1, ans, cur, nums);
cur.pop_back();
// 在不加入元素的情况下继续 dfs
dfs(pos+1, ans, cur, nums);
return;
}
vector<vector<int>> subsets(vector<int>& nums) {
vector<vector<int>> ans;
vector<int> cur;
dfs(0, ans, cur, nums);
return ans;
}
};
996.正方形数组的数目
给定一个非负整数数组 A，如果该数组每对相邻元素之和是一个完全平方数，则称这一数组为正方形数组。
返回 A 的正方形排列的数目。两个排列 A1 和 A2 不同的充要条件是存在某个索引 i，使得 A1[i] != A2[i]。示例 1：输入：[1,17,8] 输出：2 解释：[1,8,17] 和 [17,8,1] 都是有效的排列。
示例 2：输入：[2,2,2] 输出：1
class Solution {
public:
int numSquarefulPerms(vector<int>& nums) {
}
};
22.括号生成
数字 n 代表生成括号的对数，请你设计一个函数，用于能够生成所有可能的并且 有效的 括号组合。
示例 1：输入：n = 3 输出：[“((()))”,”(()())”,”(())()”,”()(())”,”()()()”]
示例 2：输入：n = 1 输出：[“()”]
分析:
1.我们总共有 n 对括号需要增加, 只需要判定清楚什么情况下括号需要增加, 什么情况下括号不能增加, 搜索的时候采取回溯
2.左括号可以任意加入, 只要有就可以加; 右括号在什么情况下是合法的? 左括号数右括号数多的情况下, 可以通过加入右括号, 配置成合法的括号
class Solution {
private:
vector<string> ans;
public:
void dfs(int lCnt, int rCnt, string& cur) {
// 都填完
if (lCnt == 0 && rCnt == 0) {
ans.push_back(cur);
return;
}
// 左括号可以任意加入, 只要有就可以加
if (lCnt > 0) {
cur.push_back('(');
dfs(lCnt - 1, rCnt, cur);
cur.pop_back();
}
// 右括号在什么情况下是合法的? 左括号数右括号数多的情况下, 可以通过加入右括号, 配置成合法的括号
if (rCnt > lCnt) {
cur.push_back(')');
dfs(lCnt, rCnt - 1, cur);
cur.pop_back();
}
return;
}
vector<string> generateParenthesis(int n) {
string cur = "";
dfs(n, n, cur);
return ans;
}
};
494.目标和
给你一个整数数组 nums 和一个整数 target 。向数组中的每个整数前添加 ‘+’ 或 ‘-‘ ，然后串联起所有整数，可以构造一个 表达式 ：
例如，nums = [2, 1] ，可以在 2 之前添加 ‘+’ ，在 1 之前添加 ‘-‘ ，然后串联起来得到表达式 “+2-1” 。
返回可以通过上述方法构造的、运算结果等于 target 的不同 表达式 的数目。示例 1：输入：nums = [1,1,1,1,1], target = 3
输出：5 解释：一共有 5 种方法让最终目标和为 3 。
-1 + 1 + 1 + 1 + 1 = 3
+1 - 1 + 1 + 1 + 1 = 3
+1 + 1 - 1 + 1 + 1 = 3
+1 + 1 + 1 - 1 + 1 = 3
+1 + 1 + 1 + 1 - 1 = 3示例 2：输入：nums = [1], target = 1 输出：1
分析:
1.遍历决策空间为对每一个元素有两种选择, +nums[i] 或者 -nums[i]
r
+1 -1
+1 -1 +1 -1
class Solution {
public:
int ans = 0;
void dfs(int pos, int sum, vector<int>& nums, int target) {
if (pos == nums.size()) {
if (sum == target) {
++ans;
}
} else {
dfs(pos + 1, sum+nums[pos], nums, target);
dfs(pos + 1, sum-nums[pos], nums, target);
}
return;
}
int findTargetSumWays(vector<int>& nums, int target) {
dfs(0, 0, nums, target);
return ans;
}
};
679.24 点游戏
给定一个长度为4的整数数组 cards 。你有 4 张卡片，每张卡片上都包含一个范围在 [1,9] 的数字。您应该使用运算符 [‘+’, ‘-‘, ‘*’, ‘/‘] 和括号 ‘(‘ 和 ‘)’ 将这些卡片上的数字排列成数学表达式，以获得值24。
你须遵守以下规则:
除法运算符 ‘/‘ 表示实数除法，而不是整数除法。例如， 4 /(1 - 2 / 3)= 4 /(1 / 3)= 12 。
每个运算都在两个数字之间。特别是，不能使用 “-” 作为一元运算符。例如，如果 cards =[1,1,1,1] ，则表达式 “-1 -1 -1 -1” 是 不允许 的。
你不能把数字串在一起 例如，如果 cards =[1,2,1,2] ，则表达式 “12 + 12” 无效。
如果可以得到这样的表达式，其计算结果为 24 ，则返回 true ，否则返回 false 。示例 1: 输入: cards = [4, 1, 8, 7] 输出: true 解释: (8-4) * (7-1) = 24
示例 2: 输入: cards = [1, 2, 1, 2] 输出: false
class Solution {
public:
bool judgePoint24(vector<int>& cards) {
}
};
17.电话号码的字母组合
给定一个仅包含数字 2-9 的字符串，返回所有它能表示的字母组合。答案可以按 任意顺序 返回。给出数字到字母的映射如下（与电话按键相同）。注意 1 不对应任何字母。
示例 1：输入：digits = “23” 输出：[“ad”,”ae”,”af”,”bd”,”be”,”bf”,”cd”,”ce”,”cf”]
示例 2：输入：digits = “” 输出：[]
示例 3：输入：digits = “2” 输出：[“a”,”b”,”c”]
分析:
1.先把所有的从数字到字母的字符串放在一个 map 里面, 然后对数字进行回溯搜索
2.回溯的对应关系为
unrorderd_map<int, char> {
{'2', "abc"},
{'3', "def"},
{'4', "ghi"},
{'5', "jkl"},
{'6', "mno"},
{'7', "pqrs"},
{'8', "tuv"},
{'9', "wxyz"}
}
3.采用回溯的思想逐个加入
class Solution {
private:
vector<string> ans;
unordered_map<char, string> num2letter{
{'2', "abc"},
{'3', "def"},
{'4', "ghi"},
{'5', "jkl"},
{'6', "mno"},
{'7', "pqrs"},
{'8', "tuv"},
{'9', "wxyz"}
};
public:
void dfs(int idx, string& cur, string& target) {
if (idx == target.size()) {
ans.push_back(cur);
return;
}
string candidates = num2letter[target[idx]];
for (int i = 0; i < candidates.size(); ++i) {
cur.push_back(candidates[i]);
dfs(idx+1, cur, target);
cur.pop_back();
}
return;
}
vector<string> letterCombinations(string digits) {
if (digits.empty()) {
return ans;
}
string cur = "";
dfs(0, cur, digits);
return ans;
}
};
39.组合总和
给你一个 无重复元素 的整数数组 candidates 和一个目标整数 target ，找出 candidates 中可以使数字和为目标数 target 的 所有 不同组合 ，并以列表形式返回。你可以按 任意顺序 返回这些组合。
candidates 中的 同一个 数字可以 无限制重复被选取 。如果至少一个数字的被选数量不同，则两种组合是不同的。
对于给定的输入，保证和为 target 的不同组合数少于 150 个。示例 1：输入：candidates = [2,3,6,7], target = 7 输出：[[2,2,3],[7]]
解释：
2 和 3 可以形成一组候选，2 + 2 + 3 = 7 。注意 2 可以使用多次。
7 也是一个候选， 7 = 7 。
仅有这两种组合。示例 2：输入: candidates = [2,3,5], target = 8 输出: [[2,2,2,2],[2,3,3],[3,5]]
示例 3：输入: candidates = [2], target = 1 输出: []
分析:
1.想一下我们的搜索空间是什么, 为了保证不重复不遗漏, 先对元素进行排序, 每次搜索的时候, 要从当前的位置开始搜索, 之前搜过的元素不去搜索, 因此除了维护求和之外, 还得维护一个当前的搜索位置
class Solution {
private:
vector<vector<int>> ans;
public:
void dfs(int sum, int startIdx, int target, vector<int>& cur, vector<int>& candidates) {
if (sum == target) {
ans.push_back(cur);
return;
}
if (sum > target) {
return;
}
for (int i = startIdx; i < candidates.size(); ++i) {
cur.push_back(candidates[i]);
dfs(sum + candidates[i], i, target, cur, candidates);
cur.pop_back();
}
return;
}
vector<vector<int>> combinationSum(vector<int>& candidates, int target) {
if (candidates.empty()) {
return ans;
}
vector<int> cur;
// 必须先排序
sort(candidates.begin(), candidates.end());
// dfs 的时候带上搜索的位置, 才能确定候选集合
dfs(0, 0, target, cur, candidates);
return ans;
}
};
698.划分为k个相等的子集
给定一个整数数组 nums 和一个正整数 k，找出是否有可能把这个数组分成 k 个非空子集，其总和都相等。
示例 1：输入： nums = [4, 3, 2, 3, 5, 2, 1], k = 4 输出： True. 说明： 有可能将其分成 4 个子集（5），（1,4），（2,3），（2,3）等于总和。
示例 2: 输入: nums = [1,2,3,4], k = 3 输出: false
分析:
1.这道题猛感觉很难, leetcode 上标记只是 medium
class Solution {
public:
bool canPartitionKSubsets(vector<int>& nums, int k) {
}
};
转载请注明来源, from goldandrabbit.github.io
