如何用Java的ArrayList返回指定格式数组以输出所有子序列？

我想要返回指定格式的数组来打印一个数组的所有子序列，期望格式如下：

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

我编写的代码：

static ArrayList<Integer> trv(ArrayList<Integer> num, int index, ArrayList<Integer> op, ArrayList<Integer> ans) {
    if (index >= num.size()) {
        // System.out.print(op);
        // System.out.println();
        ans.addAll(op);
        return ans;
    }
    // exclude
    int ele = num.get(index);
    op.add(ele);
    trv(num, index + 1, op, ans);
    op.remove(op.size() - 1);
    // include
    trv(num, index + 1, op, ans);

    return ans;
}
public static void main(String[] args) {
    ArrayList<Integer> n = new ArrayList<>();
    int index = 0;
    ArrayList<Integer> op = new ArrayList<>();
    ArrayList<Integer> ans = new ArrayList<>();

    n.add(1);
    n.add(2);
    n.add(3);
    System.out.println(trv(n, index, op, ans));
}

当前输出：

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

问题根源 #

当前ans是一维的ArrayList<Integer>，每次调用ans.addAll(op)只是把当前子序列的元素逐个追加到一维数组中，导致最终输出是扁平化的结构，而非包含多个子数组的二维数组。另外递归逻辑的注释标注错误（先添加元素是「包含当前元素」，移除后是「不包含当前元素」）。

修正方案 #

1. 将ans的类型改为ArrayList<ArrayList<Integer>>，用来存储多个子数组
2. 递归终止时，添加当前op的副本到ans中（直接添加op会因后续修改导致已存入的子序列被改变）
3. 修正递归逻辑的注释，避免混淆

修正后的代码：

import java.util.ArrayList;

public class Subsequence {
    static ArrayList<ArrayList<Integer>> trv(ArrayList<Integer> num, int index, ArrayList<Integer> op, ArrayList<ArrayList<Integer>> ans) {
        if (index >= num.size()) {
            // 存入op的副本，防止后续操作影响已保存的子序列
            ans.add(new ArrayList<>(op));
            return ans;
        }
        // 包含当前元素
        int ele = num.get(index);
        op.add(ele);
        trv(num, index + 1, op, ans);
        op.remove(op.size() - 1);
        // 不包含当前元素
        trv(num, index + 1, op, ans);

        return ans;
    }

    public static void main(String[] args) {
        ArrayList<Integer> n = new ArrayList<>();
        int index = 0;
        ArrayList<Integer> op = new ArrayList<>();
        ArrayList<ArrayList<Integer>> ans = new ArrayList<>();

        n.add(1);
        n.add(2);
        n.add(3);
        System.out.println(trv(n, index, op, ans));
    }
}

最终输出 #

运行后将得到符合期望的结果：

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

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