Bài Tập Java Số 17: Liệt Kê Các Tập Con

Đề bài

Viết chương trình liệt kê tất cả các tập con k phần tử của 1, 2, ..,n (k≤n). Input: n,k∈ N Output: tất cả các tập con k phần tử của 1,2,...n.

Giải thuật

Ta sử dụng thuật toán quay lui để thực hiện bài toán trên. Đây là một chiến lược tìm kiếm lời giải cho các bài toán thỏa mãn ràng buộc. Người đầu tiên đề ra thuật ngữ này (backtrack) là nhà toán học người Mỹ D. H. Lehmer vào những năm 1950.

Code mẫu

package baitap17;

import java.util.Scanner;

public class baitap17 {

    public static void ketqua(int a[], int k)
    {
       System.out.print("{");
       for(int i=1; i<=k;i++)
       {
         if(i==k)
           System.out.println(a[i]+"}");
         else
           System.out.print(a[i]+",");
       }
    }
    public static void callback (int a[],int n, int k, int i)
    {
       for(int j=a[i-1]+1;j<=n-k+i;j++)
       {
         a[i]=j;
         if(i==k)
           ketqua(a,k);
         else
           callback(a,n,k,i+1);
       }
    }
    public static void main(String[] args) {
       int n,k;
       Scanner nhap = new Scanner(System.in);
       System.out.println("Nhap so n");
       n = nhap.nextInt();
       System.out.println("Nhap so phan tu cua tap con cua 1,2...,n");
       k = nhap.nextInt(); 
       while(k>n)
       {
         System.out.println("k phai nho hon hoac bang n. Nhap lai");
         k = nhap.nextInt(); 
       }
         int a[]= new int[n+1];
         a[0]=0;
         int i=1;
         callback(a,n,k,i);
   }
}