DSA-Collection/SubsetProblem.java at main · ferdyfebriyanto/DSA-Collection · 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
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
class Main

{

    // Returns true if there exists a subsequence of `A[0…n]` with the given sum

    public static boolean subsetSum(int[] A, int n, int k)

    {

        // return true if the sum becomes 0 (subset found)

        if (k == 0) {

            return true;

        }


        // base case: no items left, or sum becomes negative

        if (n < 0 || k < 0) {

            return false;

        }


        // Case 1. Include the current item `A[n]` in the subset and recur

        // for the remaining items `n-1` with the remaining total `k-A[n]`

        boolean include = subsetSum(A, n - 1, k - A[n]);


        // Case 2. Exclude the current item `A[n]` from the subset and recur for

        // the remaining items `n-1`

        boolean exclude = subsetSum(A, n - 1, k);


        // return true if we can get subset by including or excluding the

        // current item

        return include || exclude;

    }


    // Subset Sum Problem

    public static void main(String[] args)

    {

        // Input: a set of items and a sum

        int[] A = { 7, 3, 2, 5, 8 };

        int k = 14;


        if (subsetSum(A, A.length - 1, k)) {

            System.out.print("Subsequence with the given sum exists");

        }

        else {

            System.out.print("Subsequence with the given sum does not exist");

        }

    }