递归生成子集如何避免生成重复的子集

递归生成子集时，为了避免生成重复的子集，可以采用以下策略：

1. **排序**：首先对原始数组进行排序，这样可以确保在递归过程中，相同的元素是连续的，从而便于在生成子集时避免重复。

2. **使用标记数组**：可以使用一个布尔数组（标记数组）来记录哪些元素已经被选择加入当前子集，这样在递归的每一层都可以根据这个标记数组来决定是否将某个元素加入子集。

3. **控制递归**：在递归函数中加入判断条件，比如当尝试加入的元素与前一个元素相同时，只有当它未被标记时才加入子集，这样可以避免重复。

下面是一个简单的递归生成子集的伪代码示例，其中包含了避免生成重复子集的逻辑：

function generateSubsets(arr, index, currentSubset, allSubsets, used) {
    if (index == arr.length) {
        allSubsets.add(new ArrayList(currentSubset)); // 将当前子集添加到结果集合中
        return;
    }

    // 不包含当前元素
    generateSubsets(arr, index + 1, currentSubset, allSubsets, used);

    // 包含当前元素，但需确保当前元素与前一个元素不同或前一个元素未被使用
    if (index > 0 && arr[index] == arr[index - 1] && !used[index - 1]) {
        return; // 避免重复
    }
    used[index] = true; // 标记当前元素已使用
    currentSubset.add(arr[index]); // 将当前元素加入子集
    generateSubsets(arr, index + 1, currentSubset, allSubsets, used); // 继续递归
    currentSubset.remove(currentSubset.size() - 1); // 回溯，移除当前元素
    used[index] = false; // 取消标记
}

// 调用示例
ArrayList<ArrayList<Integer>> allSubsets = new ArrayList<>();
boolean[] used = new boolean[arr.length]; // 用于标记是否使用了某个元素
Arrays.sort(arr); // 对数组进行排序
generateSubsets(arr, 0, new ArrayList<>(), allSubsets, used);

在这个示例中，`arr`是输入数组，`allSubsets`是存储所有子集的集合，`currentSubset`是当前正在构建的子集，`used`是标记数组，用于记录哪些元素已经被用于构建子集。