[数据结构与算法]组合去重——三数之和

给你一个包含 n 个整数的数组 nums，判断 nums 中是否存在三个元素 a，b，c ，使得 a + b + c = 0 ？请你找出所有和为 0 且不重复的三元组。

未去重未剪枝代码：

	public void hanshu(List<List<Integer>> result,List<Integer> path,int[] nums,int startIndex,int sum,){
        if(path.size()==3){
            if(sum==0)
                result.add(new ArrayList<>(path));//每次add都得新建一个path
            return;
        }
        for(int i=startIndex;i<nums.length;i++){//除非找到之后break，否则它还会继续找，所以不用担心找到后就不往后继续找
            sum+=nums[i];
            path.add(nums[i]);
            hanshu(result,path,nums,i+1,sum);//这儿是i+1不是startIndex+1
            path.remove(path.size()-1);
            sum-=nums[i];
        }
    }

去重加剪枝代码：

	public static void hanshu(List<List<Integer>> result,List<Integer> path,int[] nums,int startIndex,int sum,boolean[] flag){
        if(path.size()==3){
            if(sum==0){
                result.add(new ArrayList<>(path));
            }
            return;
        }
        for(int i=startIndex;i<nums.length&&nums[i] + sum <= 0;i++){//nums[i] + sum <= 0为剪枝操作
            if(i>0&&nums[i-1]==nums[i]&& !flag[i - 1])
                continue;//同一树层用过，那就不能用该元素
            flag[i]=true;
            sum+=nums[i];
            path.add(nums[i]);
            hanshu(result,path,nums,i+1,sum,flag);
            path.remove(path.size()-1);
            sum-=nums[i];
            flag[i]=false;//因为这步完了是for循环的下一个索引，即同一树层的下一个节点，所以告诉大家这层你被用过了
        }
    }

总结

• 没有break的话，会找完所有的路径，所以不用担心找到后就不往后继续找。
  有break那就不会找完所有路径，所以break可以用来剪枝。
• 递归函数传参是是i+1不是startIndex+1
• 每次add都得新建一个path，否则每次加进去的是同一个path
• 剪枝就是让少循环，没必要进循环的别进，或者在循环里的让提前退出。&&nums[i] + sum <= 0为前者，break为后者
• 元素在同一个组合内是可以重复的，怎么重复都没事，但两个组合不能相同。
  所以我们要去重的是同一树层上的“使用过”，同一树枝上的都是一个组合里的元素，不用去重。
• 强调一下，树层去重的话，需要对数组排序！