Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- 6 + 13 = 19
- 13 + 3 + 3 = 19
- Enter positive integers terminated with 0: 6 13 3 3 0
- Enter the desired sum: 19
- Solution 1:6 +13 =19
- Solution 2: 13 +3 +3 =19
- Found 2 solutions
- public static boolean SubSetSum(int start, int[] nums, int target) {
- if (start >= nums.length) {
- return (target == 0);
- }
- if (SubSetSum(start + 1, nums, target - nums[start])) {
- System.out.println( nums[start] );
- return true;
- }
- if (SubSetSum(start + 1, nums, target)) {
- return true;
- }
- return false;
- }
- public static void main(String[] args) {
- int[] mySet = {4,1,3,2};
- int sum = 5;
- System.out.println("The Goal is : " + sum);
- SubSetSum(0,mySet, sum) ;
- }
- }
- import java.util.ArrayList;
- import java.util.Arrays;
- import java.util.HashSet;
- import java.util.List;
- import java.util.Set;
- class ResursionTest {
- public static void findSubsets(Set<List<Integer>> allSubsets, List<Integer> nums) {
- if (nums.size() == 0) {
- return;
- }
- // add the current list as a possibility
- allSubsets.add(new ArrayList<>(nums));
- // then add a possibility that has one less
- for (int i = 0; i < nums.size(); i++) {
- final List<Integer> subset = new ArrayList<>(nums);
- subset.remove(i);
- findSubsets(allSubsets, subset);
- }
- }
- public static void main(String[] args) {
- final Integer[] array = {4, 1, 3, 2};
- final HashSet<List<Integer>> allSubsets = new HashSet<>();
- findSubsets(allSubsets, Arrays.asList(array));
- System.out.println(allSubsets);
- }
- }
- [[3, 2], [1], [4, 3], [2], [3], [1, 2], [4, 3, 2], [1, 3], [4], [4, 1, 2], [4, 1, 3], [4, 1, 3, 2], [4, 1], [1, 3, 2], [4, 2]]
- import java.util.ArrayList;
- import java.util.Arrays;
- import java.util.HashSet;
- import java.util.List;
- import java.util.Set;
- class ResursionTest {
- public static void findSubsets(Set<List<Integer>> allSubsets, List<Integer> nums, int sum) {
- if (nums.size() == 0) {
- return;
- }
- int currentSum = 0;
- for (Integer num : nums) {
- currentSum += num;
- }
- // does the current list add up to the needed sum?
- if (currentSum == sum) {
- allSubsets.add(new ArrayList<>(nums));
- }
- for (int i = 0; i < nums.size(); i++) {
- final List<Integer> subset = new ArrayList<>(nums);
- subset.remove(i);
- findSubsets(allSubsets, subset, sum);
- }
- }
- public static void main(String[] args) {
- int sum = 5;
- final Integer[] array = {4, 1, 3, 2};
- final HashSet<List<Integer>> allSubsets = new HashSet<>();
- findSubsets(allSubsets, Arrays.asList(array), sum);
- System.out.println(allSubsets);
- }
- }
- [[3, 2], [4, 1]]
- public static void main(String[] args) {
- Scanner sc = new Scanner(System.in);
- int t = sc.nextInt();
- while(t-->0){
- int n = sc.nextInt();
- int arr[] = new int[n];
- for(int i = 0;i<n;i++){
- arr[i] = sc.nextInt();
- }
- int target = sc.nextInt();
- int dp[] = new int[target+1];
- dp[0] = 1;
- int currSum = 0;
- for(int i = 0;i<n;i++){
- currSum += arr[i];
- for(int j = Math.min(currSum,target);j>= arr[i];j--){
- dp[j] += dp[j-arr[i]];
- }
- }
- System.out.println(dp[target]);
- }
- }
Add Comment
Please, Sign In to add comment