1863.md

1863. 找出所有子集的异或总和再求和

示例 1：

输入：grid = [[0,6,0],[5,8,7],[0,9,0]]
输出：24
解释：
[[0,6,0],
 [5,8,7],
 [0,9,0]]
一种收集最多黄金的路线是：9 -> 8 -> 7。

示例 2：

输入：grid = [[1,0,7],[2,0,6],[3,4,5],[0,3,0],[9,0,20]]
输出：28
解释：
[[1,0,7],
 [2,0,6],
 [3,4,5],
 [0,3,0],
 [9,0,20]]
一种收集最多黄金的路线是：1 -> 2 -> 3 -> 4 -> 5 -> 6 -> 7。

分析阶段

1、问题类型

第二类：对某种数结构和算法的使用

使用的算法：在给定的元素集合中，找到元素满足条件的组合，使用“回溯算法“

数据结构：回溯算法需要构建空间状态树，使用树结构

2、解题思路

IP地址由4段数字组成：A.B.C.D，求解该题就是在在一个字符串中，确定IP地址中每一段数字，在字符串中对应的返回。

方法 $backtrack(res,path,s,ipSeg,start)$ 表示：在字符串 $s$ 中，从下标 $start$ 开始，查找IP中的第 $ipSeg (0 \le ipSeg \le 3)$ 段的数据。

接下来，确定“回溯算法”必需的一些要素，最后用代码实现。

（1）选择列表

整个字符串作为备选的元素，通过符号 "." 来划分字符串，每个元素只能使用一次。

（2）路径

记录 IP 中每段数字。

（3）结束条件

当 $ipSeg\gt 3$ 时，表示 IP 地址的所有段数字都已经确定了，这时要根据 $start$ 来判断是直接结束，还是把路径添加到结果集中：

• 如果 $start == s.length()$，表示字符串中所有元素都已经遍历过，可以把路径添加到结果集中
• 否则，就丢弃当前路径

（4）选择

什么条件下才把当前遍历的数字添加到路径中？

根据 IP 地址的要求，数字满足下面条件才能添加进路径：

• 位数在[1,3]之间
• 值在[0,255] 之间
• 如果只有1位，可以以 0 开头
• 如果超过1位，不能以 0 开头

（5）空间状态树

下图中字符串为 “101023”。

编码阶段

class Solution {

    public static void main(String[] args) {
        int[] nums = new int[]{1, 3};

        System.out.println(new Solution().subsetXORSum(nums));

    }

    public int subsetXORSum(int[] nums) {
        List<List<Integer>> res = new LinkedList<>();

        dfs(res, nums, new LinkedList<>(), 0);
        return computeOxr(res);
    }


    private void dfs(List<List<Integer>> res, int[] nums, List<Integer> path, int idx) {
        if (idx == nums.length) {
            res.add(new ArrayList<>(path));
            return;
        }
        res.add(new ArrayList<>(path));

        for (int i = idx; i < nums.length; i++) {
            path.add(nums[i]);
            dfs(res, nums, path, i + 1);
            path.remove(path.size() - 1);
        }
    }

    private int computeOxr(List<List<Integer>> res) {
        int sum = 0;
        for (List<Integer> sub : res) {
            if (sub.size() == 0) {
                continue;
            }
            int tmp = sub.get(0);
            for (int i = 1; i < sub.size(); i++) {
                tmp = tmp ^ sub.get(i);
            }
            sum += tmp;
        }
        return sum;
    }
}

class Solution {

    public static void main(String[] args) {
        int[] nums = new int[]{1, 3};

        System.out.println(new Solution().subsetXORSum(nums));

    }

    private int sum = 0;

    public int subsetXORSum(int[] nums) {
        if (nums.length == 0) {
            return sum;
        }
        dfs(nums, 0, 0);
        return sum;
    }
    
    private void dfs(int[] nums, int oxr, int idx) {
        if (idx == nums.length) {
            sum += oxr;
            return;
        }

        dfs(nums, oxr ^ nums[idx], idx + 1);
        dfs(nums, oxr, idx + 1);
    }
}

总结阶段

从字符串中生成IP地址，相当于在一个字符数组中依次遍历字符找出有效的IP组合，使用“回溯算法”求解。