题解 | #牛牛的三元组问题#

import java.util.*;


public class Solution {
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     * 
     * @param nums int整型一维数组 
     * @return int整型二维数组
     */
    public int[][] findTriplets (int[] nums) {
        // write code here
        Arrays.sort(nums);
        List<Integer> path=new ArrayList<>();
        List<int[]> list=new ArrayList<>();
        boolean[] used=new boolean[nums.length];
        backTrack(0, used, nums, path, list);
        return list.toArray(new int[list.size()][3]);
    }

    private void backTrack(int start, boolean[] used, int[] nums,
     List<Integer> path, List<int[]> list){
        if(path.size()==3){
            int sum=path.get(0)+path.get(1)+path.get(2);
            if(sum==0){
                int[] tmp=new int[3];
                for (int i = 0; i < 3; i++)
                    tmp[i] = path.get(i);
                list.add(tmp);
            }
            return;
        }
        for(int i=start; i<nums.length; i++){
            if(used[i] || i>0 && nums[i-1]==nums[i] &&!used[i-1])continue;
            
            used[i]=true;
            path.add(nums[i]);
            backTrack(i, used, nums, path, list);
            used[i]=false;
            path.remove(path.size()-1);

        }
    }
}

这道题目和力扣上的数组组合问题十分相似，只是变了一个说法，这题要求按字典序返回，所以我们要联想到排序，这样每次取到的数字都是按照顺序的，另外为了保证结果不重复，也要把下一次开始的位置记录下来传到下一个递归过程，并且使用used数组标记使用过的元素。