Java实现有序子集生成：对ArrayList的ArrayList按指定顺序排序

你的递归代码当前是在遍历完所有元素后才将子集加入结果，导致生成顺序是从最长子集到空集，和需求不符。要实现指定的顺序（空集→[1]→[1,2]→[1,2,3]→[1,3]→[2]→[2,3]→[3]），需要调整递归逻辑：每进入递归就先记录当前子集，再依次选择后续元素进行递归回溯。

修改后的完整代码 #

import java.util.ArrayList;

class Solution {
    public static void subsetsRec(ArrayList<Integer> A, ArrayList<Integer> curr, int start, ArrayList<ArrayList<Integer>> res) {
        // 先将当前子集加入结果集
        res.add(new ArrayList<>(curr));
        
        // 从start位置开始遍历后续元素，避免重复子集
        for (int i = start; i < A.size(); i++) {
            // 选择当前元素加入临时子集
            curr.add(A.get(i));
            // 递归处理下一个位置的元素
            subsetsRec(A, curr, i + 1, res);
            // 回溯，移除当前元素
            curr.remove(curr.size() - 1);
        }
    }

    public static ArrayList<ArrayList<Integer>> subsets(ArrayList<Integer> A) {
        ArrayList<Integer> curr = new ArrayList<>();
        ArrayList<ArrayList<Integer>> res = new ArrayList<>();
        subsetsRec(A, curr, 0, res);
        return res;
    }

    // 测试用例
    public static void main(String[] args) {
        ArrayList<Integer> input = new ArrayList<>();
        input.add(1);
        input.add(2);
        input.add(3);
        ArrayList<ArrayList<Integer>> result = subsets(input);
        for (ArrayList<Integer> subset : result) {
            System.out.println(subset);
        }
    }
}

代码逻辑说明 #

1. 子集记录时机调整：进入递归函数后立即将当前临时子集curr的副本加入结果集，这样空集会被第一个加入，后续每一步递归都会先记录当前状态的子集。
2. 遍历与递归逻辑：从start位置开始遍历元素，确保每个子集都是按元素顺序生成（不会出现[2,1]这类逆序子集），同时避免重复生成相同子集。
3. 回溯操作：在递归返回后移除刚加入的元素，回到上一层状态，继续尝试选择下一个元素生成新的子集。

运行测试用例后，输出顺序完全符合需求：

[]
[1]
[1, 2]
[1, 2, 3]
[1, 3]
[2]
[2, 3]
[3]

内容的提问来源于stack exchange，提问作者sigma