open_source_start/SubsetSum.java at master · bhavesh1235/open_source_start · GitHub

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
import java.util.Scanner;

/* A Dynamic Programming solution for subset,
This code solves the problem in
Pseudo-polynomial time use the Dynamic programming.


*/
class SubsetSUm {


    static boolean isSubsetSum(int set[],
                               int n, int sum)
    {

        boolean subset[][] = new boolean[sum + 1][n + 1];

        for (int i = 0; i <= n; i++)
            subset[0][i] = true;


        for (int i = 1; i <= sum; i++)
            subset[i][0] = false;


        for (int i = 1; i <= sum; i++) {
            for (int j = 1; j <= n; j++) {
                subset[i][j] = subset[i][j - 1];
                if (i >= set[j - 1])
                    subset[i][j] = subset[i][j] || subset[i - set[j - 1]][j - 1];
            }
        }

        return subset[sum][n];
    }

    /* Driver code */
    public static void main(String args[])
    { Scanner sc = new Scanner(System.in);
        System.out.print("Enter the size of your array:");
        int n = sc.nextInt();

        int set[] = new int [n];

        System.out.println("Enter your array:");
        for (int i = 0; i < n; i++)
         set[i] =sc.nextInt();

        System.out.println("Enter the sum:");
        int sum = sc.nextInt();

        if (isSubsetSum(set, n, sum) == true)
            System.out.println("Found a subset"
                               + " with given sum");
        else
            System.out.println("No subset with"
                               + " given sum");

         sc.close();
    }
}