93.复原IP地址

【思路】

确定终止条件

IP一共有三个逗点，也就说明树的高度（深度）一共为3，那么当逗点为3时，前三个IP字段为合法字段，我们就需要对最后一个IP字段进行判断是否为合法ip字段，如果合法则说明当前整个路径path为一个合法IP，添加入结果集即可。
Java实现

class Solution {
    List<String> res = new ArrayList<>();
    StringBuilder sb = new StringBuilder();
    public List<String> restoreIpAddresses(String s) {
        dps(s,0,0);
        return res;
    }

    public void dps(String s ,int start ,int number){
        if(start == s.length() && number == 4){
            res.add(sb.toString());
            return ;
        }
        if(start == s.length() || number == 4){
            return ;
        }
        for(int i = start;i< s.length() && i-start < 3 &&Integer.parseInt(s.substring(start,i+1))>=0 &&
        Integer.parseInt(s.substring(start,i+1)) <= 255 ; i++){
            if(i+1 - start > 1 && s.charAt(start) -'0' == 0){
                continue;
            }
            sb.append(s.substring(start,i+1));
            if(number < 3){
                sb.append(".");
            }
            number++;
            dps(s,i+1,number);
            number--;
            sb.delete(start+number,i+number+2);
        }
    }
}

Go实现

var(
    path []string
    res []string
)
func restoreIpAddresses(s string) []string {
    path,res = make([]string,0,len(s)),make([]string,0)
    dfs(s,0)
    return res
}
func dfs(s string,start int){
   if len(path) == 4{
       if start == len(s){
            str := strings.Join(path,".")
            res  = append(res,str)
       }
       return
   }
    
   for i := start;i<len(s);i++{
        if i!= start && s[start] == '0'{
           break
        }
        str := s[start:i+1]
        num,_ := strconv.Atoi(str)
        if num >=0 && num <= 255{
            path = append(path,str)
            dfs(s,i+1)
            path = path[:len(path)-1]
        }else{
            break
        }
    }
}

78.子集

文章：11. 子集问题

题目：78. 子集

Java实现

class Solution {
    List<List<Integer>> res = new ArrayList<>();
    LinkedList<Integer> path = new LinkedList<>();
    public List<List<Integer>> subsets(int[] nums) {
        dfs(nums,0);
        return res;
    }
    public void dfs(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]);
           dfs(nums,i+1);
           path.removeLast();
       }
    }
}

Go实现

func subsets(nums []int) [][]int {
    res := make([][]int,0)
    path := make([]int,0,len(nums))
    var dfs func(nums []int,start int)
    dfs = func(nums []int , start int){
        //值传递。地址被修改
        //res = append(res,path)
        tmp := make([]int,len(path))
        copy(tmp,path)
        res = append(res,tmp)
        if start >= len(nums){
            return
        }
        for i:= start;i<len(nums);i++{
            path = append(path,nums[i])
            dfs(nums,i+1)
            path = path[:len(path)-1]
        }
    }
    dfs(nums,0)
    return res
}

90.子集II

文章：13. 子集II

题目：90. 子集 II

Java实现

class Solution {
    List<List<Integer>> res = new ArrayList<>();
    LinkedList<Integer> path = new LinkedList<>();
    public List<List<Integer>> subsetsWithDup(int[] nums) {
        //记得排序
        Arrays.sort(nums);
        dfs(nums,0);
        return res;
    }
    public void dfs(int[] nums,int startIndex){
        //类型不一样，要new一个
        //res.add(path);
        res.add(new ArrayList<>(path));
        for(int i = startIndex;i<nums.length;i++){
            if(i != startIndex && nums[i] == nums[i-1]){
                continue;
            }
            path.add(nums[i]);
            dfs(nums,i+1);
            path.removeLast();
        }

    }
}

Go实现

func subsetsWithDup(nums []int) [][]int {
    res := make([][]int,0)
    path := make([]int,0,len(nums))
    sort.Ints(nums)
    var dfs func(nums []int,start int)
    dfs = func(nums []int , start int){
        //值传递。地址被修改
        //res = append(res,path)
        tmp := make([]int,len(path))
        copy(tmp,path)
        res = append(res,tmp)
        
        for i:= start;i<len(nums);i++{
            if i!= start && nums[i-1] == nums[i]{
                continue

            }
                path = append(path,nums[i])
                dfs(nums,i+1)
                path = path[:len(path)-1]
            
            
        }
    }
    dfs(nums,0)
    return res
}