FilesExpand file tree

 main

/

Subset_Sum_Problem.java

Copy path

Blame

More file actions

Blame

More file actions

Latest commit

 

History

History

History

30 lines (29 loc) · 671 Bytes

 main

/

Subset_Sum_Problem.java

Copy path

Top

File metadata and controls

• Code
• Blame

30 lines (29 loc) · 671 Bytes

Raw

Copy raw file

Download raw file

Open symbols panel

Edit and raw actions

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

/*

Dynamic Programming

Subset_Sum_Problem

*/

import java.util.*;

public class Main

{

public static void main(String[] args) {

int arr[] ={2,3,7,8,10};

int n=arr.length;

int sum=11;

System.out.println(Subset_sum(arr,n,sum));

}

// Subset_sum Using Recursion

// TC : 2^n

// SC : O(1) + ~ O(2n) --> Auxilary Space for recusive call ---

public static boolean Subset_sum(int arr[] ,int n,int sum){

if(sum==0){

return true;

}

if(sum!=0 && n==0){

return false;

}

if(arr[n-1]>sum){

return Subset_sum(arr,n-1,sum);

}

return Subset_sum(arr,n-1,sum-arr[n-1]) || Subset_sum(arr,n-1,sum) ;

}

}