本题思路：最重要的是想到一个收集结果的条件，也就是终止条件。

1. 当 . 的个数达到三个时候，并且，判断最后剩余的是否符合要求，如果符合，说明整个ip地址可以，就加入到结果集中
2. 每次分割的时候，都要判断一次是否满足合法条件，如果合法的进行下一层递归，不合法，就直接进入一个循环。
3. 单层循环完，要记得回溯！

class Solution {List<String> res = new ArrayList();public List<String> restoreIpAddresses(String s) {backtracking(s,0,0);return res;}public void backtracking(String s, int startIndex, int postnum){if(postnum == 3){if(isValid(s,startIndex,s.length()-1)){res.add(s);return;}}for(int i = startIndex; i < s.length(); i++){if(isValid(s,startIndex,i)){s = s.substring(0,i+1) + '.' + s.substring(i+1);postnum++;backtracking(s,i+2,postnum);postnum--;s = s.substring(0,i+1) + s.substring(i+2);}else{break;}}}// 检查字符串是否有效public boolean isValid(String s, int start,int end){if(start > end){return false;}if(s.charAt(start) == '0' && start != end){return false;}int sum = 0;for(int i = start; i <= end; i++){if(s.charAt(i) > '9' || s.charAt(i) < '0'){return false;}sum = sum * 10 + (s.charAt(i) - '0');if(sum > 255){return false;}}return true;}
}

本题思路：和组合问题不同的是， 本题没有个数要求，收集的结果集，所以只要遍历到，就要收集。那么就容易很多。

class Solution {List<Integer> path = new ArrayList();List<List<Integer>> res = new ArrayList();public List<List<Integer>> subsets(int[] nums) {backtracking(nums,0);return res;}public void backtracking(int[] nums, int startIndex){res.add(new ArrayList(path));if(startIndex >= nums.length){return;}for(int i = startIndex; i < nums.length; i++){path.add(nums[i]);backtracking(nums,i+1);path.remove(path.size() - 1);}}
}

本题思路：本题涉及到一个去重操作
去重操作的话，要在树层去重，树枝上不能去重。具体代码思路如下

class Solution {List<Integer> path = new ArrayList();List<List<Integer>> res = new ArrayList();public List<List<Integer>> subsetsWithDup(int[] nums) {int[] used = new int[nums.length];Arrays.sort(nums);backtracking(nums,0,used);return res;}public void backtracking(int[] nums, int startIndex,int[] used){res.add(new ArrayList(path));if(startIndex >= nums.length){return;}for(int i = startIndex; i < nums.length; i++){if( i > 0 && nums[i] == nums[i-1] && used[i-1] == 0){continue;}path.add(nums[i]);used[i] = 1;backtracking(nums,i+1,used);used[i] = 0;path.remove(path.size() - 1);}}
}