目录
找出所有子集的异或总和再求和
1863. 找出所有子集的异或总和再求和 - 力扣（LeetCode）
class Solution {
int sum;
int path;
public int subsetXORSum(int[] nums) {
dfs(nums, 0);
return sum;
}
public void dfs(int[] nums, int pos) {
sum += path;
for (int i = pos; i < nums.length; i++) {
path ^= nums[i];
dfs(nums, i + 1);
path ^= nums[i];// 恢复现场
}
}
}全排列 II
解法：先把数组进行排序。
剪枝：
- 同一个节点的所有分支中，相同的元素只能选择一次
- 同一个数只能使用一次（使用一个check进行标记）
只关心“不合法”的分支：check[i]==true||(i!=0&&nums[i]==nums[i-1]&&check[i-1]==false)
只关心“合法”的分支：check[i]==false&&(i==0||nums[i]!=nums[i-1]||check[i-1]==true)
class Solution {
List<List<Integer>> ret;
List<Integer> path;
boolean[] check;
public List<List<Integer>> permuteUnique(int[] nums) {
ret = new ArrayList<>();
path = new ArrayList<>();
check = new boolean[nums.length];
Arrays.sort(nums);
dfs(nums, 0);
return ret;
}
public void dfs(int[] nums, int pos) {
if (pos == nums.length) {
ret.add(new ArrayList<>(path));
return;
}
for (int i = 0; i < nums.length; i++) {
if (check[i] == false && (i == 0 || nums[i] != nums[i - 1] || check[i - 1] == true)) {
path.add(nums[i]);
check[i] = true;
dfs(nums, pos + 1);
// 回溯
path.remove(path.size() - 1);
check[i] = false;
}
}
}
}电话号码的字母组合
解法：
全局变量：解决数字与字符串之间的映射关系->使用字符串数组；path[]；ret[]
class Solution {
String[] hash = { "", "", "abc", "def", "ghi", "jkl", "mno", "pqrs", "tuv", "wxyz" };
List<String> ret;
StringBuffer path;
public List<String> letterCombinations(String digits) {
ret = new ArrayList<>();
path = new StringBuffer();
if (digits.length() == 0)
return ret;
dfs(digits, 0);
return ret;
}
public void dfs(String digits, int pos) {
if (pos == digits.length()) {
ret.add(path.toString());
return;
}
String cur = hash[digits.charAt(pos) - '0'];
for (int i = 0; i < cur.length(); i++) {
path.append(cur.charAt(i));
dfs(digits, pos + 1);
path.deleteCharAt(path.length() - 1);// 恢复现场
}
}
}括号生成
有效的括号组合：
- 左括号的数量==右括号的数量
- 从头开始的任意一个字串，左括号的数量>=右括号的数量
class Solution {
int left, right, n;
List<String> ret;
StringBuffer path;
public List<String> generateParenthesis(int nn) {
n = nn;
ret = new ArrayList<>();
path = new StringBuffer();
dfs();
return ret;
}
public void dfs() {
if (right == n) {
ret.add(path.toString());
return;
}
if (left < n) {
// 添加左括号
path.append('(');
left++;
dfs();
path.deleteCharAt(path.length() - 1);
left--;// 回溯
}
if (right < left) {
// 添加右括号
path.append(')');
right++;
dfs();
path.deleteCharAt(path.length() - 1);
right--;// 回溯
}
}
}组合
class Solution {
List<List<Integer>> ret;
List<Integer> path;
int n, k;
public List<List<Integer>> combine(int nn, int kk) {
n = nn;
k = kk;
ret = new ArrayList<>();
path = new ArrayList<>();
dfs(1);
return ret;
}
public void dfs(int pos) {
if (path.size() == k) {
ret.add(new ArrayList<>(path));
return;
}
for (int i = pos; i <= n; i++) {
path.add(i);
dfs(i + 1);
path.remove(path.size() - 1);// 回溯
}
}
}目标和
class Solution {
int ret, aim;
public int findTargetSumWays(int[] nums, int target) {
aim = target;
dfs(nums, 0, 0);
return ret;
}
public void dfs(int[] nums, int pos, int path) {
if (pos == nums.length) {
if (path == aim)
ret++;//
return;
}
// 加法
dfs(nums, pos + 1, path + nums[pos]);
// 减法
dfs(nums, pos + 1, path - nums[pos]);
}
}组合总和
解法一：
class Solution {
List<List<Integer>> ret;
List<Integer> path;
int aim;
public List<List<Integer>> combinationSum(int[] nums, int target) {
aim = target;
ret = new ArrayList<>();
path = new ArrayList<>();
dfs(nums, 0, 0);
return ret;
}
public void dfs(int[] nums, int pos, int sum) {
if (sum == aim) {
ret.add(new ArrayList<>(path));
return;
}
if (sum > aim || pos == nums.length)
return;
for (int i = pos; i < nums.length; i++) {
path.add(nums[i]);
dfs(nums, i, sum + nums[i]);
path.remove(path.size() - 1);// 回溯
}
}
}解法二：
class Solution {
List<List<Integer>> ret;
List<Integer> path;
int aim;
public List<List<Integer>> combinationSum(int[] nums, int target) {
aim = target;
ret = new ArrayList<>();
path = new ArrayList<>();
dfs(nums, 0, 0);
return ret;
}
public void dfs(int[] nums, int pos, int sum) {
if (sum == aim) {
ret.add(new ArrayList<>(path));
return;
}
if (sum > aim || pos == nums.length)
return;
// 枚举nums[pos] 使用多少个
for (int i = 0; i * nums[pos] + sum <= aim; i++) {
if (i != 0)
path.add(nums[pos]);
dfs(nums, pos + 1, sum + i * nums[pos]);
}
// 恢复现场
for (int i = 1; i * nums[pos] + sum <= aim; i++) {
path.remove(path.size() - 1);
}
}
}字母大小写全排列
class Solution {
List<String> ret;
StringBuffer path;
public List<String> letterCasePermutation(String s) {
ret = new ArrayList<>();
path = new StringBuffer();
dfs(s, 0);
return ret;
}
public void dfs(String s, int pos) {
if (pos == s.length()) {
ret.add(path.toString());
return;
}
char ch = s.charAt(pos);
// 不改变
path.append(ch);
dfs(s, pos + 1);
// 回溯：
path.deleteCharAt(path.length() - 1);
// 改变
if (ch >= 'A' && ch <= 'z') {
char tmp = change(ch);
path.append(tmp);
dfs(s, pos + 1);
// 回溯：
path.deleteCharAt(path.length() - 1);
}
}
public char change(char ch) {
if (ch >= 'a' && ch <= 'z')
return ch -= 32;
else
return ch += 32;
}
}优美的排列
N 皇后（难！！！）
解法：剪枝+代码能力
如何剪枝？考虑当前位置能否放上皇后
1.无脑循环（时间复杂度高）
2.类似哈希表的策略
class Solution {
boolean[] checkCol, checkDig1, checkDig2;
List<List<String>> ret;
char[][] path;
int n;
public List<List<String>> solveNQueens(int nn) {
n = nn;
checkCol = new boolean[n];
checkDig1 = new boolean[n * 2];
checkDig2 = new boolean[n * 2];
ret = new ArrayList<>();
path = new char[n][n];
for (int i = 0; i < n; i++) {
Arrays.fill(path[i], '.');
}
dfs(0);
return ret;
}
public void dfs(int row) {
if (row == n) {
// 添加结果
List<String> tmp = new ArrayList<>();
for (int i = 0; i < n; i++)
tmp.add(new String(path[i]));
ret.add(new ArrayList<>(tmp));
}
for (int col = 0; col < n; col++) {
// 判断能不能放
if (checkCol[col] == false && checkDig1[row - col + n] == false && checkDig2[row + col] == false) {
path[row][col] = 'Q';
checkCol[col] = checkDig1[row - col + n] = checkDig2[row + col] = true;
dfs(row + 1);
// 恢复现场
path[row][col] = '.';
checkCol[col] = checkDig1[row - col + n] = checkDig2[row + col] = false;
}
}
}
}