给定一个整数数组（长度为 n），使用 Java 中的递归查找并 return 输入数组的所有子集

Question

假设我的输入数组是 [15,20,12] 所需答案是二维数组
所需的输出如下
[12
20
20 12
15
15 12
15 20
15 20 12
]

Answer 1

给你。

public static void main(String[] args) {

    int[] nums= {15, 20, 12};
    int[][] subsets = subsets(nums);
    for (int i = 1; i < subsets.length; i++) {
        System.out.println(Arrays.toString(subsets[i]));
    }
}

public static int[][] subsets(int input[]) {
    List<List<Integer>> list = new ArrayList<>();
    subsetsHelper(list, new ArrayList<>(), input, 0);
    return convertListToArray(list);
}

private static void subsetsHelper(List<List<Integer>> list , List<Integer> resultList, int [] nums, int start){
    list.add(new ArrayList<>(resultList));
    for(int i = start; i < nums.length; i++){
       // add element
        resultList.add(nums[i]);
       // Explore
        subsetsHelper(list, resultList, nums, i + 1);
       // remove
        resultList.remove(resultList.size() - 1);
    }
}

private static int[][] convertListToArray(List<List<Integer>> list) {
    int[][] array = new int[list.size()][];
    for (int i = 0; i < array.length; i++) {
        array[i] = new int[list.get(i).size()];
    }
    for(int i=0; i<list.size(); i++){
        for (int j = 0; j < list.get(i).size(); j++) {
            array[i][j] = list.get(i).get(j);
        }
    }
    return array;

}

1.As每次递归调用都会在此处表示子集，将resultList（见上面的递归代码）添加到每次调用的子集列表中。 2.Iterate 集合的元素。 3.In 每次迭代向列表中添加元素 explore(recursion) 并使 start = i+1 遍历数组的剩余元素。从列表中删除元素

输出：

[15]
[15, 20]
[15, 20, 12]
[15, 12]
[20]
[20, 12]
[12]

Answer 2

不清楚是作业还是实际案例。这就是我如何使用 Guava PowerSet 解决它：

public static void main(String[] args) {
    Integer input[] = {15,20,12};
    List<Integer> rev = Lists.reverse(Arrays.asList(input));
    Set<Integer> indices = IntStream.range(0, input.length).boxed().collect(ImmutableSet.toImmutableSet());
    Object output[] = Sets.powerSet(indices).stream()
            .filter(indexset -> !indexset.isEmpty())
            .map(indexset -> indexset.stream().map(i -> rev.get(i)).collect(Collectors.collectingAndThen(toList(), Lists::reverse)))
            .map(List::toArray)
            .toArray();
    System.out.println(Arrays.deepToString(output));
}

Answer 3

免责声明：

这是我的原创作品。没有从任何地方复制解决方案的任何部分。
我的解决方案适用于 3 个元素。但是，这需要改进以适用于其他大小的数组。尽管如此，我还是发布了它，以便 OP 或其他任何人都可以扩展此解决方案以适用于任何大小的数组。
除了幂集不能有重复元素外，这道题和幂集很接近。如果从此问题中删除此异常，则有许多可用的解决方案，例如在 1, 2, 3 等

import java.util.Arrays;

public class Main {
    public static void main(String[] args) {
        int[] arr = { 15, 20, 12 };
        System.out.println(Arrays.deepToString(subsets(arr)));
    }

    public static int[][] subsets(int input[]) {
        int[][] subarrs = new int[(int) Math.pow(2, input.length) - 1][input.length];
        int[] indices = { 0 };
        subsetsHelper(input, subarrs, 0, 0, 0, indices);
        return subarrs;
    }

    private static void subsetsHelper(int input[], int[][] subarrs, int index, int i, int j, int[] indices) {
        if (i == input.length) {
            subarrs[index] = input;
            return;
        }
        int[] subarr = new int[indices.length];
        for (int x = 0; x < subarr.length; x++) {
            subarr[x] = input[indices[x]];
        }
        subarrs[index] = subarr;
        if (j == input.length - 1) {
            subsetsHelper(input, subarrs, index + 1, i + 1, i + 1, new int[] { i + 1 });
        } else {
            subsetsHelper(input, subarrs, index + 1, i, j + 1, new int[] { i, j + 1 });
        }
    }
}

输出：

 [[15], [15, 20], [15, 12], [20], [20, 12], [12], [15, 20, 12]]

Answer 4

public static int[][]returnallsub(int arr[], int si){

    if(si==arr.length)
    {int[][]ret=new int [1][0];
return ret;
    }
    
    
    int [][]rss =returnallsub(arr,si+1);
    int [][]tss=new int[rss.length*2][];
    
    int i=0;
for(;i<rss.length;i++) {
tss[i]=new int [rss[i].length];

}
       int k=0;
    for(;k<rss.length;k++) {
tss[i]=new int [rss[k].length+1];
  i++;
}
    
    
        int j=0;
   for(i=0;i<rss.length;i++) {
  for(j=0;j<rss[i].length;j++){
      
      tss[i][j]=rss[i][j];
  }
}
    
     for(k=i;k<tss.length;k++)  {
      tss[k][0]=arr[si];
  }
    
      int r=i;
      for(i=0;i<rss.length;i++) {
  for(j=0;j<rss[i].length;j++){
      
      tss[r][j+1]=rss[i][j];
      
  }
          r++;
} 
 return tss; 
    
    
}



public static int[][] subsets(int arr[]) {
   
     int start=0;
  return  returnallsub( arr,0);
    
    


}

}

给定一个整数数组（长度为 n），使用 Java 中的递归查找并 return 输入数组的所有子集

Given an integer array (of length n), find and return all the subsets of input array using recursion in Java

java

arrays

recursion

jagged-arrays