93. 复原 IP 地址

public class Solution {
    List<String> result = new LinkedList<>();

    LinkedList<String> cur = new LinkedList<>();

    public List<String> restoreIpAddresses(String s) {
        if (s == null || s.length() < 4 || checkNum(s)) {
            return result;
        }
        backtracking(s, 0, new StringBuilder());
        return result;
    }

    private void backtracking(String s, int beginIndex, StringBuilder stringBuilder) {
        // ip地址有几个要素，
        // 1.开始的元素是不可能等于0的，如果切割点位之后是以0开头的，并且位数超过一位，比如04，那么切割点必然不对，可以考虑返回了
        // 2.如果切割的元素大于255,是错误的
        // 3.切割的元素最大只能是3位

        // 如果beginIndex跑到了最后面，那么意味着，已经切割完成了。
        if (cur.size() == 4 && beginIndex != s.length()) {
            return;
        }
        if (beginIndex == s.length() && cur.size() == 4) {
            result.add(getSplitCur());
            return;
        }

        for (int i = beginIndex; i < s.length(); i++) { // 从beginIndex开始，最大只能是三位
            stringBuilder.append(s.charAt(i));
            // 如果满足条件，就以当前点位进行切割
            if (checkRule(stringBuilder)) {
                cur.add(stringBuilder.toString());
                backtracking(s, i + 1, new StringBuilder());
                cur.removeLast();
            }
        }
    }

    private boolean checkRule(StringBuilder stringBuilder) {
        // 注意这里是== '0'
        if ((stringBuilder.charAt(0) == '0' && stringBuilder.length() > 1) || stringBuilder.length() > 3 || (stringBuilder.length() == 3 && Integer.parseInt(stringBuilder.toString()) > 255)) {
            return false;
        }
        return true;
    }

    private String getSplitCur() {
        StringBuilder stringBuilder = new StringBuilder();
        for (int i = 0; i < cur.size() - 1; i++) {
            stringBuilder.append(cur.get(i));
            stringBuilder.append(".");
        }
        stringBuilder.append(cur.get(cur.size() - 1));
        return stringBuilder.toString();
    }

    private boolean checkNum(String s) {
        for (int i = 0; i < s.length(); i++) {
            if (s.charAt(i) < '0' && s.charAt(i) > '9') {
                return true; // 包含非数字的其他字符
            }
        }
        return false;
    }
}

这道题我磕磕碰碰了挺久，最主要的是我把点位搞错了，一直觉得是3位，实际上分割下来，数字是四个。

同时也要保证，最后切割完成，最后的list的个数是4，而不是其他的数字

78. 子集

class Solution {
    List<List<Integer>> result = new LinkedList<>();

    LinkedList<Integer> list = new LinkedList();

    public List<List<Integer>> subsets(int[] nums) {
        // 元素 互不相同  ||  1 <= nums.length <= 10 || -10 <= nums[i] <= 10
        result.add(new LinkedList<>()); // 先将空加上
        backtracking(nums, 0);
        return result;
    }

    private void backtracking(int[] nums, int beginIndex) {
        if (beginIndex == nums.length) {
            return;
        }

        for (int i = beginIndex; i < nums.length; i++) {
            list.add(nums[i]);
            result.add(new LinkedList<>(list));
            backtracking(nums, i + 1);
            list.removeLast();
        }
    }
}

子集问题很简单，就是把所有结果都加进去即可

90. 子集 II

 private List<List<Integer>> result = new LinkedList<>();

    private LinkedList<Integer> list = new LinkedList<>();

    public List<List<Integer>> subsetsWithDup(int[] nums) {
        Arrays.sort(nums);
        // 有重复数字,那么当当前元素和上一个元素相等的时候，跳过当前元素即可
        if (nums.length < 1) {
            return result;
        }

        backtracking(nums, 0);
        return result;
    }

    private void backtracking(int[] nums, int beginIndex) {
        result.add(new LinkedList<>(list));

        if (beginIndex >= nums.length) {
            return;
        }

        for (int i = beginIndex; i < nums.length; i++) {
            if (i != beginIndex && nums[i] == nums[i - 1]) {
                continue;
            }
            list.add(nums[i]);
            backtracking(nums, i + 1);
            list.removeLast();
        }
    }

也是很简单的一道题，如果前一个数和当前值重复，跳过当前数即可

记得，一定要排序