Java: Calculate all possible k-size subsets

Get all subsets of a certain size.

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

public class SetCombination {
   static void recursiveSubsets(List<int[]> sets, int s[], int k, int t[], int q, int r) {
      if (q == k) {
         int ss[] = new int[k];
         for (int i = 0; i < k; ++i) {
            ss[i] = t[i];
         }
         sets.add(ss);
      } else {
         for (int i = r; i < s.length; ++i) {
            t[q] = s[i];
            recursiveSubsets(sets, s, k, t, q + 1, i + 1);
         }
      }
   }

   public static List<int[]> subSets(int s[], int k) {
      List<int[]> list = new ArrayList<>();
      int t[] = new int[s.length];
      recursiveSubsets(list, s, k, t, 0, 0);
      return list;
   }

   public static void main(String arg[]) {
      int s[] = {1, 2, 3, 4, 5, 6};
      List<int[]> list = subSets(s, 3);
      for (int x[] : list) {
         System.out.println(Arrays.toString(x));
      }
   }
}

Prints out:
[1, 2, 3]
[1, 2, 4]
[1, 2, 5]
[1, 2, 6]
[1, 3, 4]
[1, 3, 5]
[1, 3, 6]
[1, 4, 5]
[1, 4, 6]
[1, 5, 6]
[2, 3, 4]
[2, 3, 5]
[2, 3, 6]
[2, 4, 5]
[2, 4, 6]
[2, 5, 6]
[3, 4, 5]
[3, 4, 6]
[3, 5, 6]
[4, 5, 6]

Advertisements

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s