题解 | #三数之和#

import java.util.*;


public class Solution {
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     *
     * @param num int整型一维数组
     * @return int整型ArrayList<ArrayList<>>
     */
    public ArrayList<ArrayList<Integer>> threeSum (int[] num) {
        // write code here
        // 定一个结果集
        ArrayList<ArrayList<Integer>> result = new ArrayList<>();
        // 已选元素集合
        ArrayList<Integer> temp = new ArrayList<>();
        // 排序
        Arrays.sort(num);
        getSum(num, result, temp,  0, 3, 0);
        return result;
    }

    public void getSum(int[] nums, ArrayList<ArrayList<Integer>> result,
                       ArrayList<Integer> temp, int index, int flag, int sum) {

        if (flag == 0 && sum == 0) {
            result.add(new ArrayList<>(temp));
            return;
        }
        // 元素的个数不能小于0或者大于3
        if (flag < 0 || flag > 3) {
            return;
        }

        for (int i = index; i < nums.length; i ++) {
            if (i > index && nums[i] == nums[i - 1]) {
                continue;
            } else {
                temp.add(nums[i]);
                flag--;
                sum += nums[i];
                getSum(nums, result, temp, i + 1, flag, sum);
                temp.remove(temp.size() - 1);
                flag ++;
                sum -= nums[i];
            }
        }
    }
}