LeetCode Day21 BackTracking Part 3

93. Restore IP Addresses

A valid IP address consists of exactly four integers separated by single dots. Each integer is between 0 and 255 (inclusive) and cannot have leading zeros.

For example, "0.1.2.201" and "192.168.1.1" are valid IP addresses, but "0.011.255.245", "192.168.1.312" and "192.168@1.1" are invalid IP addresses.
Given a string s containing only digits, return all possible valid IP addresses that can be formed by inserting dots into s. You are not allowed to reorder or remove any digits in s. You may return the valid IP addresses in any order.

Example 1:

Input: s = "25525511135"
Output: ["255.255.11.135","255.255.111.35"]
Example 2:

Input: s = "0000"
Output: ["0.0.0.0"]
Example 3:

Input: s = "101023"
Output: ["1.0.10.23","1.0.102.3","10.1.0.23","10.10.2.3","101.0.2.3"]

Constraints:

1 <= s.length <= 20
s consists of digits only.
Original Page

 /**0  0,1,2

        12 size
        start = 3, i= 1
        1,1,2, 2,  2,2...
        1st element = 2;
        the number of left element is : size-(start+i)
        if count*3 < size-(start+1) continue;
        */
    public List<String> restoreIpAddresses(String s) {
        List<String> list = new ArrayList<>();
        backTracking(list, new StringBuilder(), new StringBuilder(s), 0, 1);
        return list;

    }

    public void backTracking(List<String> list, StringBuilder result, StringBuilder str, int start,int count){
        if(count > 4){
            list.add(result.toString());
            return;
        }

        int size = str.length();
        for(int i=1; i<=3 && start+i<=size; i++){
            // pruning preocess, cut invalid size down before the recursion process
            if(size-start-i > (4-count)*3){
                continue;
            }

            String cur = str.substring(start, start+i);
            boolean sign = false;
            // if this number is valid or not 
            if(isValid(cur)){
                if(count!=1){
                    result.append(".");
                    sign = true;
                }
                result.append(cur);
            }else{
                continue;
            }

            backTracking(list, result, str, start+i, count+1);
            if(sign){
                result.setLength(result.length()-cur.length()-1);
            } else{
                result.setLength(result.length()-cur.length());
            }
        }
    }

    public boolean isValid(String s){
        int size = s.length();
        // valid length
        if(size<1 || size>3 ){
            return false;
        }
        // cannot have leading zeros
        if(size > 1 && s.charAt(0) == '0' ){
            return false;
        }
        // number from 0 to 255
        int num = Integer.valueOf(s);
        if(num > 255){
            return false;
        }

        return true;
    }

90. Subsets II

Given an integer array nums that may contain duplicates, return all possible
subsets
(the power set).

The solution set must not contain duplicate subsets. Return the solution in any order.

Example 1:

Input: nums = [1,2,2]
Output: [[],[1],[1,2],[1,2,2],[2],[2,2]]
Example 2:

Input: nums = [0]
Output: [[],[0]]

Constraints:

1 <= nums.length <= 10
-10 <= nums[i] <= 10

    public List<List<Integer>> subsetsWithDup(int[] nums) {
        List<List<Integer>> list = new ArrayList<>();
        List<Integer> subset = new LinkedList<>();
        list.add(new ArrayList<>());
        Arrays.sort(nums);
        backTracking(list, subset, nums, 0);


        return list;

    }
    public void backTracking (List<List<Integer>> list, List<Integer> subset, int[] nums, int start){
        if(start == nums.length){
            // list.add(new ArrayList<>(subset));
            return;
        }

        for(int i=start; i<nums.length; i++){
            if(i!=start && nums[i] == nums[i-1]){
                continue;
            }
            subset.add(nums[i]);
            list.add(new ArrayList<>(subset));
            backTracking(list, subset, nums, i+1);
            subset.remove(subset.size()-1);
        }
    }