How to create all possible subsets of size k from an array of size n (no repeats)?

Question

So I have an array of doubles. I want to find a subset within this array of size k, and store all those not in the subset into a different subarray. I want to do this for all possible subsets, without repetition.

What is the best approach?

double[] sample = {
  1.0, 3.0, 1.6, 2.1, 2.5, 2.7, 2.3, 1.5, 1.1, 0.5, 2.0, 2.0, 1.2, 1.2, 1.3, 0.5, 1.4, 2.4
};

public static void main(String[] args) {
  ArrayList < double[] > list = new ArrayList < double[] > ();
  double[] noo = pickNRandom(sample);
  if (!list.contains(noob)) { //here I want to make sure that it is a unique   subset
    list.add(noob);
    for (double a: noob) {
      System.out.print(a + " ");
    }
    System.out.println("");
  }
}

public static double[] pickNRandom(double[] lst) { //finding a random subset
  double[] i = lst;
  Collections.shuffle(Arrays.asList(i));
  double[] fin = {
    i[0], i[1], i[2], i[3], i[4], i[5], i[6], i[7]
  };
  return fin;
}

Here is a good starting point: http://stackoverflow.com/questions/4640034/calculating-all-of-the-subsets-of-a-set-of-numbers — user3707125, Dec 06 '15 at 02:55

score 1 · Answer 1 · answered Oct 01 '20 at 12:20

Here is a recursive method to create a set of all k subsets for a given array of integers:

import java.util.ArrayList;

public class Solution {
    public static void ksubsets(int[] arr, int left, int idx,
                                ArrayList<Integer> curArr, ArrayList<ArrayList<Integer>> result) {
        if (left <= 0) {
            ArrayList<Integer> tmp = new ArrayList<>(curArr);
            result.add(tmp);
            return;
        }
        for (int i = idx; i < arr.length; i++) {
            curArr.add(arr[i]);
            ksubsets(arr, left - 1, i + 1, curArr, result);
            curArr.remove(curArr.size() - 1);
        }
    }

    public static void main(String[] args) {
        int[] arr = {1, 2, 3, 4};
        int left = 3; // specifies the subset size
        int idx = 0;
        ArrayList<Integer> curArr = new ArrayList<>();
        ArrayList<ArrayList<Integer>> result = new ArrayList<>(); // contains all calculated subsets
        Solution.ksubsets(arr, left, idx, curArr, result);
        System.out.println(result.size());
    }
}

After the method ksubsets(...) is executed the result contains following ArrayLists:

1,2,3

1,2,4

1,3,4

2,3,4

There are all distinct subsets of size 3 of a set of size 4.

Thank you, this is basically what I needed. I would love to have a solution without recursion, but I don't really know how to do this myself and am not going to spend the time to make it if it's possible. — Ac Hybl, Oct 14 '22 at 18:56

score 0 · Answer 2 · answered Dec 06 '15 at 03:02

I would recommend two possible ways to approach this problem, which is a variation of the subset sum problem (an NP-complete problem that cannot be solved in polynomial time). The two approaches are:

rescursion
dynamic programming

the recursion method is easier to understand, but the dynamic programming method is more efficient and elegant. I would recommend taking a look at this site, and adapting the solutions to fit your problem (instead of summing, add subsets to your subarray).

How to create all possible subsets of size k from an array of size n (no repeats)?

2 Answers2