力扣77.组合 
class Solution { List<List<Integer>>ret=new ArrayList<>(); List<Integer>path=new ArrayList<>(); int n; int k; public List<List<Integer>> combine(int _n, int _k) { n=_n; k=_k; dfs(1); return ret; } public void dfs(int pos){ if(path.size()==k){ ret.add(new ArrayList<>(path)); return ; } //模拟画递归图的时候，有个地方没有思考清楚，就是加入说他刚开始是1，2，那么还会出现一次1，2，我刚开始想 //这怎么能对呢，明明1，2重复了 //后来才想到，是回溯想错了，应该是当他回溯的时候，就回到原先的dfs处，所以当他1，2存完之后，他是i还是2 for(int i=pos;i<=n;i++){ path.add(i); dfs(i+1); path.remove(path.size()-1); } } }
力扣494.目标和
刚开始我一直在思考一件事，就是我的薄弱代码能力，怎么表示加号和减号
后来发现，其实发现这就是我的思维和编程思维的区别
我的思维总在想把符号添加到数字身上，如何如何，其实编程的思维体现在哪，就是说这种加不加符号，完全可以转化成——运算符的加减法
假如说是加号，那就是两数相加，假如说减号那么就是两数字相减
class Solution { int ret; int sum; int path; public int findTargetSumWays(int[] nums, int target) { path=target; dfs(nums,0); return ret; } public void dfs(int []nums,int pos){ if(pos==nums.length){ if(path==sum){ ret++; } return ; } sum+=nums[pos]; dfs(nums,pos+1); sum=sum-nums[pos]; sum=sum-nums[pos]; dfs(nums,pos+1); sum+=nums[pos]; } }
全局变量写成参数的写法（这个时候就不用回溯了，怎么选择使用看自己，代码简洁，就是把记录全部数字当成参数）
class Solution { int ret; int path; public int findTargetSumWays(int[] nums, int target) { path=target; dfs(nums,0,0); return ret; } public void dfs(int []nums,int pos,int sum){ if(pos==nums.length){ if(path==sum){ ret++; } return ; } dfs(nums,pos+1,sum+nums[pos]); dfs(nums,pos+1,sum-nums[pos]); } }
力扣39.组合总和
剪枝只需要剪掉这个位置之前的位置即可，从pos开始，剪枝完成
然后递归是递归的下标
class Solution { List<List<Integer>>ret=new ArrayList<>(); List<Integer>path=new ArrayList<>(); int sum; int k; public List<List<Integer>> combinationSum(int[] candidates, int target) { k=target; dfs(candidates,0); return ret; } public void dfs(int[]candidates,int pos){ if(sum==k){ ret.add(new ArrayList<>(path)); return; } if(sum>k){ return; } //这个操作for是横着走 for(int i=pos;i<candidates.length;i++){ sum+=candidates[i]; path.add(candidates[i]); //我们递归之后往下走，我认为传递的值，是为了回溯之后使用， //传递i是为了让他可以往下着走，pos相当于是横着的。 //下一层接着从i位置开始，假如说是pos那么它就会重复的进入一个地点多次，比如进了假如你已经存完了223此时，你回溯之后还是进入23由于pos一直不变，所以你又选了一个2这样就是重复了，我认为他选pos还是i的意义是用来回溯之后看往哪里走的. dfs(candidates,i); path.remove(path.size()-1); sum-=candidates[i]; } } }
这个是吧sum当成参数而不是全局变量
class Solution { List<List<Integer>>ret=new ArrayList<>(); List<Integer>path=new ArrayList<>(); int k; public List<List<Integer>> combinationSum(int[] candidates, int target) { k=target; dfs(candidates,0,0); return ret; } public void dfs(int[]candidates,int pos,int sum){ if(sum==k){ ret.add(new ArrayList<>(path)); return; } if(sum>k){ return; } //这个操作for是横着走 for(int i=pos;i<candidates.length;i++){ path.add(candidates[i]); //我们递归之后往下走，我认为传递的值，是为了回溯之后使用， //传递i是为了让他可以往下着走，pos相当于是横着的。 //下一层接着从i位置开始， dfs(candidates,i,sum+candidates[i]); path.remove(path.size()-1); } } }
解法2:
class Solution { List<List<Integer>>ret=new ArrayList<>(); List<Integer>path=new ArrayList<>(); int k; public List<List<Integer>> combinationSum(int[] candidates, int target) { k=target; dfs(candidates,0,0); return ret; } public void dfs(int[]candidates,int pos,int sum){ if(sum==k){ ret.add(new ArrayList<>(path)); return; } if(sum>k||pos==candidates.length){ return; } //这个操作for是横着走,pos来做下标 for(int i=0;i*candidates[pos]+sum<=k;i++){ if(i!=0)path.add(candidates[pos]); dfs(candidates,pos+1,sum+i*candidates[pos]); } //回溯是把哪个情况列举完，再去恢复现场 //恢复现场 for(int i=1;i*candidates[pos]+sum<=k;i++){ path.remove(path.size()-1); } } }
力扣784.字母大小写全排列
我的代码能力还是弱，但是能知道他的一些思想
，确实画出图来，更容易去想
首先先说我的第一个困扰，就是字符串操作，我不是很会用字符串，因为他的各个方法已经一些东西，她这个转换成大写，我以为是在字符串上操作，没想到仅仅是我使用
char ch=s.charAt(pos); 使用一个字符，然后存储的是字符，pos在这里代表下标，
其次第二个困扰：怎么判断他是数字还是字符，我开始是想用ascll码，但是我又想到ascll也是数字，然后我也开始想过0-9但是我又否认了，因为我在想数字假如说是11，这种两位数不久错误了吗，我又突然醒悟，我字符串是一个一个取的，就算三位数111，他也是一个1一个1的取，换句话说数字就只有0-9，那么就是判断字符<0或者>9的时候不合格，然后字符A和a差一律32。
String修改不方便，以后都是使用StringBuffer用来修改字符串
class Solution { List<String>ret=new ArrayList<>(); StringBuffer path=new StringBuffer(); public List<String> letterCasePermutation(String s) { dfs(s,0); return ret; } public void dfs(String s,int pos){ if(path.length()==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<'0'||ch>'9'){ //发生改变 if(ch>='a'&&ch<='z'){ ch-=32; }else{ ch+=32; } path.append(ch); dfs(s,pos+1); path.deleteCharAt(path.length()-1); } } }
