查找產品等於給定目標的int數組的所有子集

Question

給定目標產品號，從int數組中填充產品與目標產品相同的所有子集。

例如：

Target product is 12. 

An int array is { 1, 3, 1, 2, 2, 1,2,4 }. 

Then all satisfied subsets whose product is 12 are as follows: 

12 = 1*3*1*2*2 
12 = 3*2*2*1*1*1 
12 = 4*3*1*1*1 

Answer 1

public class Subset { 
public static int PROD = 12; 

public static void main(String[] args) { 
    int arr[] = { 1, 3, 1, 2, 2, 1, 2, 4 }; 
    boolean visited[] = new boolean[arr.length]; 
    function(arr, 0, 1, visited); 

} 

public static void function(int a[], int index, int prod, boolean visited[]) { 
    if (prod == PROD) { 
     print(a, visited); 
    } 
    if (index > a.length - 1) 
     return; 
    function(a, index + 1, prod, visited); 
    visited[index] = true; 
    function(a, index + 1, prod * a[index], visited); 
    visited[index] = false; 
} 

private static void print(int[] a, boolean[] visited) { 

    for (int i = 0; i < a.length; i++) { 
     if (visited[i] == true) { 
      System.out.print(a[i] + " "); 
     } 

    } 
    System.out.println(); 
} 

}