Lập trình Java - 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
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).
Mã nguồn chương trình:
import java.util.Scanner;
public class Bai12 {
public static int nhap(){
Scanner input= new Scanner(System.in);
boolean check= false;
int n=0;
while(!check){
System.out.print(" ");
try{
n= input.nextInt();
check= true;
}catch(Exception e){
System.out.println("Ban phai nhap so! hay nhap lai...");
input.nextLine();
}
}
return (n);
}
public static void result(int a[],int k){
int i;
System.out.println();
for(i=1 ; i<=k ; i++){
System.out.print(" "+a[i]);
}
}
public static void try_backTrack(int a[], int n, int k, int i){
int j;
for(j=a[i-1]+1 ; j<=(n-k+i) ; j++){
a[i]= j;
if(i== k) result(a,k);
else try_backTrack(a, n, k, i+1);
}
}
public static void main(String[] args) {
System.out.println("Nhap n");
int n= nhap();
int[] array= new int[n+1];
int k;
System.out.println("Liet ke tat ca cac tap con k phan tu cua 1,2,..,"+n+" : ");
for(k=1 ; k<=n ; k++){
System.out.println("\n Tap con "+k+" phan tu: ");
try_backTrack(array,n,k,1);
}
}
}
Kết quả:
Nhap n
5
Liet ke tat ca cac tap con k phan tu cua 1,2,..,5 :
Tap con 1 phan tu:
1
2
3
4
5
Tap con 2 phan tu:
1 2
1 3
1 4
1 5
2 3
2 4
2 5
3 4
3 5
4 5
Tap con 3 phan tu:
1 2 3
1 2 4
1 2 5
1 3 4
1 3 5
1 4 5
2 3 4
2 3 5
2 4 5
3 4 5
Tap con 4 phan tu:
1 2 3 4
1 2 3 5
1 2 4 5
1 3 4 5
2 3 4 5
Tap con 5 phan tu:
1 2 3 4 5