关于LeetCode78题的剪枝问题

Question

波波老师好，我在做78号问题的时候，自己觉得用上了剪枝，但是执行用时没有提高，希望老师看下我的代码

LeetCode 78题地址：https://leetcode-cn.com/problems/subsets/submissions/

下面是我的代码：

class Solution {
    public List<List<Integer>> subsets(int[] nums) {
        if (nums == null ||nums.length == 0) return new ArrayList<>();

         Arrays.sort(nums);
        List<List<Integer>> res = sets(nums);
        res.add(new ArrayList<>());
        return res;
    }

    private List<List<Integer>> sets(int[] nums) {

        List<List<Integer>> res = new ArrayList<>();

        // 终止条件
        if (nums == null || nums.length == 0) return res;

        int len = nums.length;
        if (len == 1) {
            List list = new ArrayList();
            list.add(nums[0]);
            res.add(list);

            return res;
        }

        // 递归条件
        for (int i = 0; i < len; i++) {
            List list = new ArrayList();
            list.add(nums[i]);
            res.add(list);
               
            if (i + 1 == len) { // 剪枝操作
                break;
            }
            
            int[] newDate = newDate(nums, i, len);
            List<List<Integer>> result = sets(newDate);
            for (int j = 0; j < result.size(); j++) {
                result.get(j).add(nums[i]);
                res.add(result.get(j));
            }
        }

        return res;
    }

    private int[] newDate(int[] nums, int i, int len) {
        int[] newDate = new int[len - i - 1];
        for (int j = i + 1; j < len; j++) {
            newDate[j - i - 1] = nums[j];
        }

        return newDate;
    }
}

Answer 1

liuyubobobo 2020-06-03 13:06:47

你这个剪枝剪掉的“枝”太小了。

因为如果没有这个剪枝，把i == len - 1 带进 newDate 里，那个 for 循环根本不会执行。所以其实你只是把空转一下 newDate 变成了对 i + 1 == len 的判断，并不会减掉一整棵子树。这种剪枝在有的情况下反而性能会下降，因为你的 if 是在 for 循环中，对大多数情况都增加了新的判断的性能开销，但实际剪掉不去执行的代码并不多。

继续加油！：）

• 提问者 冲哥_ #1

  嗯嗯，谢谢老师。我再修改下代码结构看看。