回溯总结

/**
 * <a href="https://leetcode.cn/problems/combinations/discussion/">...</a>
 * 没有额外条件属于基础回溯题目
 * @author ZVerify
 * @since 2022/11/07 11:39
 **/
public class 组合 {

    // 每次的结果
    List<Integer> list =  new ArrayList<>();
    // 最终的结果
    List<List<Integer>> result = new ArrayList<>();
    public List<List<Integer>> combine(int n, int k) {

        // 进入递归
        backtrack(1,n,k);
        return result;
    }

    private void backtrack(int start, int end, int length) {
        // 长度到了就结束
        if (list.size() == length) {
            result.add(new ArrayList<>(list));
        }

        for (int i = start; i <= end; i++) {
            // 添加
            list.add(i);
            // 递归
            backtrack(i+1, end, length);
            // 回溯
            list.remove(list.size() - 1);
        }
    }


}

/**
 * 组合总和
 * @author ZVerify
 * @since 2022/11/13 09:37
 * @see <a href="https://leetcode.cn/problems/combination-sum/">...</a>
 **/
public class 组合总和 {

    // 返回值
    List<List<Integer>> result = new ArrayList<>();
    // 结果集
    List<Integer> list = new ArrayList<>();
    int sum = 0;

    public List<List<Integer>> combinationSum(int[] candidates, int target) {


        backTracking(candidates,target,0);
        Arrays.sort(candidates);
        return result;
    }

    private void backTracking(int[] candidates, int target, int startIndex) {

        if (sum == target) {
            // 相等的时候添加
            result.add(new ArrayList<>(list));
            return;
        }

        for (int j = startIndex; j < candidates.length; j++) {

            // 如果大于的话直接退出此层，因为已经排好序了，后边肯定都会大的
            if (sum+candidates[j]>target) break;
            sum+=candidates[j];
            list.add(candidates[j]);
            backTracking(candidates,target,j);
            // 回溯
            sum-=candidates[j];
            list.remove(list.size()-1);
        }
    }

}

/**
 * 组合总和II
 * @author ZVerify
 * @since 2022/11/13 10:15
 * @see <a href="https://leetcode.cn/problems/combination-sum-ii/">...</a>
 **/
public class 组合总和II {

    // 结果集
    List<List<Integer>> result = new ArrayList<>();
    // 中间数据
    List<Integer> list = new ArrayList<>();
    // 保存记录是否使用过
    boolean[] map = null;

    // sum
    int sum = 0;
    public List<List<Integer>> combinationSum2(int[] candidates, int target) {

        Arrays.sort(candidates);

        map = new boolean[candidates.length];

        backTracking(candidates,target,0);

        return result;
    }

    private void backTracking(int[] candidates, int target, int i) {

        //满足添加
        if (sum == target) {
            result.add(new ArrayList<>(list));
            return;
        }

        for (int j = i; j < candidates.length;j++) {
            // 超过直接将这个树层断开
            if (sum+candidates[j]>target) {
                break;
            }
            // 如果当前不为树层的第一个值然后和前边的相等并且当前树枝没有使用过直接树枝断开(树层去重)
            if (j>0 && map[j] == map[j-1] && !map[j-1]) {
                continue;
            }
            map[j] = true;
            sum+=candidates[j];
            list.add(candidates[j]);
            // 递归
            backTracking(candidates,target,j+1);
            // 回溯
            map[j] = false;
            sum-=candidates[i];
            list.remove(list.size()-1);

        }

    }
}

/**
 * 组合总和III
 * @author ZVerify
 * @since 2022/11/11 20:16
 * @see <a href="https://leetcode.cn/problems/combination-sum-iii/">...</a>
 **/
public class 组合总和III {

    List<List<Integer>> result = new ArrayList<>();
    List<Integer> list = new ArrayList<>();
    int sum = 0;
    public List<List<Integer>> combinationSum3(int k, int n) {

        backtrack(n,k,1);

        return result;
    }

    private void backtrack(int n, int k, int startIndex) {

        // 等于的时候并且里边有k个数则添加
        if (sum==n && list.size()==k) {
            result.add(new ArrayList<>(list));
        }
        // 1-9
        for (int j = startIndex; j <=9; j++) {
            // 大于的时候直接树枝剪掉
            if (sum+j > n) continue;
            sum+=j;
            list.add(j);
            // 递归进入下一层
            backtrack(n,k,j+1);
            // 回溯
            sum-=j;
            list.remove(list.size()-1);

        }
    }
}

/**
 * @author ZVerify
 * @since 2022/11/12 16:22
 * @see <a href="https://leetcode.cn/problems/letter-combinations-of-a-phone-number/description/">...</a>
 **/
public class 电话号码的组合 {

    List<String> result = new ArrayList<>();
    StringBuilder temp = new StringBuilder();
    public List<String> letterCombinations(String digits) {

        if(digits==null || digits.length()==0) return result;

        // 值map
        String[] map = new String[] {"","","abc", "def", "ghi", "jkl", "mno", "pqrs", "tuv", "wxyz"};

        backtrack(digits, map , 0);
        return result;
    }

    private void backtrack(String digits, String[] map, int startIndex) {

        // 遍历完字符串结束
        if (startIndex == digits.length()) {
            result.add(temp.toString());
            return;
        }

        // 按顺序拿到字符，然后得到所对应的字符串
        char c1 = digits.charAt(startIndex);
        String s = map[c1-'0'];
        // 遍历当前的字符串然后对下一个字符所对应的每一个字符进行匹配
        for (int i = 0; i < s.length(); i++) {
            // 拿到当前案件的第i个字符
            char c = s.charAt(i);
            temp.append(c);
            // 进入下一次去拿第二个按键的字符
            backtrack(digits,map,startIndex+1);
            // 回溯
            temp.deleteCharAt(temp.length() - 1);
        }
    }


}

/**
 * @author ZVerify
 * @since 2022/11/13 16:38
 * @see <a href="https://leetcode.cn/problems/restore-ip-addresses/description/">...</a>
 **/
public class 复原IP地址 {

    // 保存结果
    List<String> result = new ArrayList<>();
    // 保存中间结果
    LinkedList<String> list = new LinkedList<>();

    public List<String> restoreIpAddresses(String s) {
        // 不符合规范直接返回null
        if (s.length()>12) return Collections.emptyList();

        backtrack(s,0);
        return result;
    }

    private void backtrack(String s, int startIndex) {
        // 当到达结尾的时候恰好是四个数则正确
        if (startIndex == s.length() && list.size()==4) {
            result.add(toResult(list));
            return;
        }

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

            String str = s.substring(startIndex,i+1);
            // 如果当前要判断的不符合直接修剪掉
            if(!isValid(str)) continue;
            // 添加
            list.addLast(str);
            // 递归
            backtrack(s, i+1);
            // 回溯
            list.pollLast();
        }

    }

    public String toResult(Deque<String> path){
        StringBuilder sb = new StringBuilder();
        for(int i = 0; i < path.size(); i++){
            sb.append(list.get(i));
            if(i != path.size() - 1)
                sb.append(".");
        }
        return sb.toString();
    }
    public boolean isValid(String s){
        if(s.length()==1) return true;
        if(s.length()>3) return false;
        if(s.charAt(0) == '0') return false;
        if(Integer.parseInt(s) > 255) return false;
        return true;
    }
}

/**
 * 这道题是最简单的子集问题了抽象树中的所有节点全部都要添加
 * @author ZVerify
 * @since 2022/11/15 08:49
 * @see <a href="https://leetcode.cn/problems/subsets/">...</a>
 **/
public class 子集问题 {

    // 返回结果
    List<List<Integer>> results = new ArrayList<>();
    // 中间结果
    List<Integer> list = new ArrayList<>();
    public List<List<Integer>> subsets(int[] nums) {

        // 递归操作
        backtrack(nums,0);
        return results;
    }

    private void backtrack(int[] nums, int startIndex) {
        // 没有任何条件约束 所以全添加
        results.add(new ArrayList<>(list));
        // 当前到达最后一个数据结束递归
        if (startIndex == nums.length) return;

        for (int i = startIndex; i < nums.length; i++) {
            list.add(nums[i]);
            // 进入下一层递归
            backtrack(nums,i+1);
            // 回溯
            list.remove(list.size() - 1);
        }
    }
}

/**
 * 子集II
 * @author ZVerify
 * @since 2022/11/15 09:17
 * @see <a href="https://leetcode.cn/problems/subsets-ii/description/">...</a>
 **/
public class 子集II {
    // 最后结果
    List<List<Integer>> result = new ArrayList<>();
    // 返回结果
    List<Integer> list = new ArrayList<>();

    public List<List<Integer>> subsetsWithDup(int[] nums) {
        Arrays.sort(nums);
        // 字典用于剪枝
        boolean[] mapInts = new boolean[nums.length];
        backtrack(nums,0,mapInts);
        return result;
    }

    private void backtrack(int[] nums, int startIndex,boolean[] map) {
        // 去重
        result.add(new ArrayList<>(list));

        // 终止
        if (nums.length == startIndex) return;

        for (int i = startIndex; i < nums.length; i++) {
            // 树层要去重
            if (i>0 && nums[i] == nums[i-1] && !map[i-1]) continue;
            map[i] = true;
            list.add(nums[i]);
            // 下一层
            backtrack(nums,i+1,map);
            // 回溯
            list.remove(list.size() - 1);
            map[i] = false;
        }
    }
}

/**
 * 递增子序列
 * @author ZVerify
 * @since 2022/11/15 11:27
 * @see <a href="https://leetcode.cn/problems/increasing-subsequences/description/">...</a>
 **/
public class 递增子序列 {

    // 结果集
    List<List<Integer>> result = new ArrayList<>();
    // 中间结果
    List<Integer> list = new ArrayList<>();

    public List<List<Integer>> findSubsequences(int[] nums) {

        backtrack(nums,0);
        return result;
    }

    private void backtrack(int[] nums, int startIndex) {
        // 当前不为一个值的时候就添加，因为在进入之前就已经进行了剪枝所以可以直接添加
        if (list.size() >1) {
            result.add(new ArrayList<>(list));
        }

        // 字典，因为我们此时要树层剪枝,但是当前不是有序的，因为要考虑递增所以不能排序要用set
        HashSet<Integer> set = new HashSet<>();

        for (int i = startIndex; i < nums.length; i++) {
            // 如果当前集合为null说明是第一个数据直接添加
            // 不为null的时候判断该层有没有出现过或者当前的值有没有上一个值大
            // 因为这里考虑了如果相同大小的数字的话也是相同的所以不加等于
            if (!list.isEmpty() && nums[i] < list.get(list.size() - 1) || set.contains(nums[i])) continue;
            set.add(nums[i]);
            list.add(nums[i]);
            // 递归
            backtrack(nums, i + 1);
            // 回溯
            list.remove(list.size() - 1);
        }

    }

}

/**
 * 全排列
 * @author ZVerify
 * @since 2022/11/15 21:07
 * @see <a href="https://leetcode.cn/problems/permutations/">...</a>
 **/
public class 全排列 {

    // 最终结果返回值
    List<List<Integer>> result = new ArrayList<>();
    // 中间结果
    List<Integer> list = new ArrayList<>();

    public List<List<Integer>> permute(int[] nums) {
        boolean[] map =  new boolean[nums.length];
        if (nums.length == 0) return null;
        backtrack(nums, map);
        return result;
    }

    private void backtrack(int[] nums, boolean[] map) {
        if (list.size() == nums.length) result.add(new ArrayList<>(list));

        for (int i = 0; i < nums.length; i++) {

            if (map[i]) continue;
            map[i] = true;
            list.add(nums[i]);
            backtrack(nums, map);
            list.remove(list.size() - 1);
            map[i] = false;
        }

    }
}

/**
 * 全排列II
 * @author ZVerify
 * @since 2022/11/16 08:34
 * @see <a href="https://leetcode.cn/problems/permutations/discussion/">...</a>
 **/
public class 全排列II {

    // 返回数据
    List<List<Integer>> result = new ArrayList<>();
    // 中间结果
    List<Integer> list = new ArrayList<>();
    // 去重用
    boolean[] map = null;

    public List<List<Integer>> permuteUnique(int[] nums) {
        if (nums.length == 0) return null;
        map = new boolean[nums.length];
        // 排序
        Arrays.sort(nums);
        backtrack(nums);
        return result;
    }

    private void backtrack(int[] nums) {
        // 遍历结束
        if (list.size() == nums.length) {
            result.add(new ArrayList<>(list));
        }

        for (int i = 0; i < nums.length; i++) {
            // 这个涉及到了双向去重，这里处理数层去重的剪枝
            if (list.size() > 1 && nums[i] == nums[i - 1] && !map[i - 1]) continue;

            // 这里处理树枝去重的剪枝，如果当中树枝上我们的值已经用过了直接剪短
            if (!map[i]) {
                map[i] = true;
                list.add(nums[i]);
                backtrack(nums);
                // 回溯
                map[i] = false;
                list.remove(list.size() - 1);
            }
        }
    }
}