返回目录

给你一个整数数组nums，其中可能包含重复元素，请你返回该数组所有可能的子集，不能包含重复的子集，子集可以按任意顺序排列

1）示例1：
输入: [1,2,2]
输出: [[],[1],[1,2],[1,2,2],[2],[2,2]]
2）示例2：
输入: [0]
输出: [[],[0]]

Python源码

def solution(arr):
    lists = [[]]  # 初始化一个空列表作为初始元素

    # 从输入列表中移除重复元素并遍历唯一元素
    unique_elements = list(set(arr))

    for integer in unique_elements:
        objects = [integer]  # 创建包含每个唯一元素的列表
        lists.append(objects)  # 将包含唯一元素的列表添加到结果中

    # 生成输入列表中元素的组合
    for i in range(len(arr)):
        sublist = [arr[i]]  # 从输入列表中选择一个元素作为起始点

        # 从当前元素开始生成组合
        for j in range(i+1, len(arr)):
            sublist.append(arr[j])  # 将后续元素添加到当前组合中
            lists.append(sublist[:])  # 将当前组合的副本添加到结果中

    return lists  # 返回包含所有组合的列表


# 测试 solution 函数
arr = [1, 2, 2]
print(solution(arr))

C语言源码

#include <stdio.h>
#include <stdlib.h>

// 生成组合的函数
int** findCombinations(int arr[], int n, int* count) {
    // 初始化一个空列表作为初始元素
    int** lists = (int **)malloc(sizeof(int *));
    *count = 1;

    lists[0] = NULL;

    // 从输入数组中移除重复元素并遍历唯一元素
    int* unique_elements = (int *)malloc(n * sizeof(int));
    int unique_count = 0;
    for (int i = 0; i < n; i++) {
        int is_unique = 1;
        for (int j = 0; j < unique_count; j++) {
            if (arr[i] == unique_elements[j]) {
                is_unique = 0;
                break;
            }
        }
        if (is_unique) {
            unique_elements[unique_count++] = arr[i];
        }
    }

    // 生成输入数组中元素的组合
    for (int i = 0; i < unique_count; i++) {
        int integer = unique_elements[i];
        int* objects = (int *)malloc(sizeof(int));
        objects[0] = integer;
        lists = (int **)realloc(lists, (*count + 1) * sizeof(int *));
        lists[*count] = objects;
        (*count)++;
    }

    // 生成输入数组中元素的组合
    for (int i = 0; i < n; i++) {
        int* sublist = (int *)malloc(sizeof(int));
        sublist[0] = arr[i];

        for (int j = i + 1; j < n; j++) {
            sublist = (int *)realloc(sublist, (j - i + 1) * sizeof(int));
            for (int k = i, l = 0; k <= j; k++, l++) {
                sublist[l] = arr[k];
            }
            lists = (int **)realloc(lists, (*count + 1) * sizeof(int *));
            lists[*count] = sublist;
            (*count)++;
        }
    }

    free(unique_elements);
    return lists;
}

int main() {
    int arr[] = {1, 2, 2};
    int n = sizeof(arr) / sizeof(arr[0]);
    int count;
    int** combinations = findCombinations(arr, n, &count);

    // 打印组合
    for (int i = 0; i < count; i++) {
        printf("[ ");
        if (combinations[i] != NULL) {
            int* combination = combinations[i];
            for (int j = 0; combination[j]; j++) {
                printf("%d ", combination[j]);
            }
            free(combination);
        }
        printf("]\n");
    }

    free(combinations);
    return 0;
}

Java源码

import java.util.ArrayList;
import java.util.List;

public class CombinationGenerator {

    // 生成组合的函数
    public static List<List<Integer>> generateCombinations(int[] arr) {
        List<List<Integer>> lists = new ArrayList<>();
        int n = arr.length;
        int maxSize = 1 << n; // 计算组合的最大数量（2的n次方）

        // 将第一个元素初始化为空列表
        lists.add(new ArrayList<>());

        // 遍历数组中的每个元素
        for (int i = 0; i < n; i++) {
            // 使用当前元素创建新的组合
            List<Integer> combination = new ArrayList<>();
            combination.add(arr[i]);
            lists.add(combination);

            // 从当前元素开始生成组合
            for (int j = i + 1; j < n; j++) {
                // 将每个现有组合扩展到后续元素
                List<Integer> sublist = new ArrayList<>();
                for (int k = i; k <= j; k++) {
                    sublist.add(arr[k]);
                }
                lists.add(sublist);
            }
        }

        return lists;
    }

    public static void main(String[] args) {
        int[] arr = {1, 2, 2};
        List<List<Integer>> combinations = generateCombinations(arr);

        // 打印组合
        for (List<Integer> combination : combinations) {
            System.out.println(combination);
        }
    }
}