class Solution {
    List<String> res = new ArrayList<>();
    LinkedList<String> path = new LinkedList<>();
    
    public List<String> restoreIpAddresses(String s) {
        backTrack(s,0);
        return res;
    }

    void backTrack(String s, int index) {
        if (path.size() == 4 && index == s.length()) {
            res.add(String.join(".",path));
        }

        for (int i = index; i < s.length(); i++) {
            if (!isValid(s, index, i)) {
                continue;
            }
            if (path.size() >= 4) {
                break;
            }
            path.addLast(s.substring(index, i+1));
            backTrack(s,i+1);
            path.removeLast();
        }
    }

    boolean isValid(String s, int start, int end) {
        int length = end-start + 1;

        if (start > end) {
            return false;
        }

        if (length == 0||length > 4) {
            return false;
        }

        if (length == 1) {
            return true;
        }

        if (s.charAt(start) == '0') {
            return false;
        }

        if (length<=2) {
            return true;
        }

        if (Integer.parseInt(s.substring(start,start+length)) > 255) {
            return false;
        } else {
            return true;
        }
    }
}

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

    void backTrack(int nums[], int index) {
        
        res.add(new ArrayList<>(path));

        for (int i = index; i < nums.length; i++) {
            path.add(nums[i]);
            backTrack(nums,i+1);
            path.removeLast();
        }
    }
}

class Solution {
    List<List<Integer>> res = new ArrayList<>();
    LinkedList<Integer> path = new LinkedList<>();
    boolean[] used;

    public List<List<Integer>> subsetsWithDup(int[] nums) {
        if (nums.length == 0){
            res.add(path);
            return res;
        }
        Arrays.sort(nums);
        used = new boolean[nums.length];
        backTrack(nums,0);
        return res;
    }

    void backTrack (int[] nums, int index) {

        res.add(new ArrayList<>(path));

        for (int i = index; i < nums.length; i++) {
            if (i>0 && nums[i] == nums[i-1] && !used[i-1]) {
                continue;
            }
            path.add(nums[i]);
            used[i] = true;
            backTrack(nums,i+1);
            path.removeLast();
            used[i] = false;
        }
    }
}