1. 火柴拼接
LC：200题
给一串数组，问这些数能否组成正方形。
思路：
副中心点寻找策略：将中心点加到每条边上面，每个边加上数又称为新的副中心点，形成新的递归策略。
class Solution {
private boolean dfs(int[] nums,int i,int l1,int l2,int l3,int l4,int sum){
// 拼接火柴的策略
if(i == nums.length){
if(l1 == sum && l2 == sum && l3 == sum && l4 == sum)
return true;
else
return false;
}
if(l1 > sum || l2 > sum || l3 > sum || l4 > sum){
return false;
}
return dfs(nums,i+1,l1+nums[i],l2,l3,l4,sum) || dfs(nums,i+1,l1,l2 + nums[i],l3,l4,sum)|| dfs(nums,i+1,l1,l2,l3 + nums[i],l4,sum) || dfs(nums,i+1,l1,l2,l3,l4 + nums[i],sum);
}
public boolean makesquare(int[] nums) {
if(nums.length == 0)
return false;
int sum = 0;
for(int i : nums){
sum += i;
}
if(sum % 4 != 0)
return false;
int l1 = 0,l2 = 0,l3 = 0,l4 = 0;
return dfs(nums,0,l1,l2,l3,l4,sum/4);
}
}
LC：51题
N皇后问题。
分析：这个题的递归策略是写出来了，但是漏掉了对角线上的标记访问问题。
class Solution {
List<List<String>>result = new ArrayList<>();
List<String>ans = new ArrayList<>();
public void dfs(int n,boolean[] y,boolean[] w,boolean[] wc,StringBuffer sb,int i){
if(i == n){
result.add(new ArrayList<>(ans));
//System.out.print("进入截至条件");
return;
}
for(int j = 0;j < n;j++){
if(y[j] || w[n-1-i+j] || wc[i+j]){
continue;
}
y[j] = true;
w[n-1-i+j] = true;
wc[i + j] = true;
ans.add(new StringBuffer(sb).replace(j,j+1,"Q").toString());
dfs(n,y,w,wc,sb,i+1);
ans.remove(i);
y[j] = false;
w[n-1-i+j] = false;
wc[i+j] = false;
}
}
public List<List<String>> solveNQueens(int n) {
StringBuffer sb = new StringBuffer();
for(int i = 0;i < n;i++){
sb.append(".");
}
dfs(n,new boolean[n],new boolean[2 * n - 1],new boolean[2 * n - 1],sb,0);
return result;
}
}
原文：https://www.cnblogs.com/jihuabai/p/11754111.html