Day 21 回溯法part03| LeetCode 93. 复原 IP 地址，78.子集，90.子集II

93. 复原 IP 地址

93. 复原 IP 地址

class Solution {

        List<String> res=new ArrayList<>();
        public List<String> restoreIpAddresses(String s) {

            backtracking(s,0,0);
            return res;
        }
        void backtracking(String s,int startIndex, int point)
        {
            if(point==3) //深度为3就截止,3个逗点、四个字串
            {
                //需要对最后一个子串进行合法性判断
                String s1=s.substring(startIndex,s.length());//左闭右闭
                if(isValid(s1))
                {
                    res.add(s);
                }

                return;
            }
            for(int i=startIndex;i<s.length();i++)

            {
                   //字串区间 [startIndex,i]
                String s2=s.substring(startIndex,i+1);//substring 是左闭右开的,因此需要+1
                if(isValid(s2))
                {
                    s=s.substring(0,i+1)+"."+s.substring(i+1);

                    point++;
                    backtracking(s,i+2,point);//上一层加了一个‘0’，因此需要+2才可以到达第二层

                     s=s.substring(0,i+1)+s.substring(i+2);
                    point--;

                }
                else
                {
                    break;
                }
            }


        }
         //合法性判断
        boolean isValid(String s)
        {
            //长度
            if(s.length()>3||s.length()==0) return false;

            //大于255
                    int num=Integer.parseInt(s);
                    if(num>255) return false;
            //前导存在0
                    String s3=String.valueOf(num);
                    if(s3.equals(s))
                    {
                        return true;
                    }
                    else
                    {
                        return false;

                    }

           
        }
    }

78.子集

78. 子集

  class Solution {
        public  List<Integer> path=new LinkedList<>();
        public  List<List<Integer>> res=new ArrayList<>();
        public List<List<Integer>> subsets(int[] nums) {
            backtraking(nums,0);
            return res;

        }
        void backtraking(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]);

                    backtraking(nums,i+1);

                    path.remove(path.size()-1);

            }
        }
    }

90.子集||

90. 子集 II

 class Solution {
        public  List<Integer> path=new LinkedList<>();
        public  List<List<Integer>> res=new ArrayList<>();

        public List<List<Integer>> subsetsWithDup(int[] nums) {
                Arrays.sort(nums);
            backtraking(nums,0);
            return res;
        }

        void backtraking(int[] nums,int startIndex)
        {
            res.add(new ArrayList<>(path));
           
            if(startIndex>=nums.length){
                return;
            }
            for(int i=startIndex;i<nums.length;i++)
            {
                //去重
                if(i>startIndex&& nums[i]==nums[i-1]) continue;
                    path.add(nums[i]);

                    backtraking(nums,i+1);

                    path.remove(path.size()-1);

            }
        }
    }