dynamic_programming/SubsetSum.java at master · rrohitramsen/dynamic_programming · 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
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
package com.program.dynamic.programming;

import java.util.Arrays;
import java.util.HashMap;
import java.util.Map;

/**
 * @author rrohit
 */
public class SubsetSum {

	/**
	 * Time : O(n-log-n)
	 * Space : O(1)
	 * @param arr
	 * @param sum
	 * @return
	 */
	public static boolean subsetSum(int arr[], int sum){

		if (sum == 0 | arr.length == 0) {
			return true;
		}

		if (arr.length == 1) {
			return arr[0] == sum;
		}

		Arrays.sort(arr);

		int tempSum=0;
		int left = 0, right = arr.length-1;

		while(left <= right){
			tempSum = arr[left] + arr[right];
			if (tempSum == sum) {
				System.out.println("Arr = [ "+arr[left]+" ] ["+arr[right]+"]  = "+tempSum);
				return true;
			}else if (tempSum > sum) {
				right--;
			}else {
				left++;
			}
		}
		return false;
	}


	/**
	 * Time : O(n)
	 * Space : O(n)
	 * @param arr
	 * @param sum
	 * @return
	 */
	public static boolean subsetSumMap(int arr[], int sum) {

		if (arr.length == 0 || sum == 0) {
			return true;
		}

		if (arr.length == 1) {
			return arr[0] == sum;
		}

		Map<Integer, Integer> pairMap = new HashMap<>();

		for (int i=0; i<arr.length; i++) {

			if (pairMap.containsKey(arr[i])) {
				return true;
			}
			pairMap.put(sum-arr[i], arr[i]);
		}

		return false;
	}

	/**
	 * Time : O(n-log-n)
	 * Space : O(1)
	 * @param arr
	 * @param sum
	 * @return
	 */
	public static void subsetSumPairs(int arr[], int sum){

		if (arr.length == 0) {
			System.out.println("Empty Array");
			return;
		}

		if (arr.length == 1 && arr[0] == sum) {
			System.out.println("Pair = "+arr[0]);
			return;
		}

		Arrays.sort(arr);

		int tempSum = 0;
		int left = 0, right = arr.length-1;

		while (left <= right) {
			tempSum = arr[left] + arr[right];
			if (tempSum == sum) {
				System.out.println("Arr = [ "+arr[left]+" ] ["+arr[right]+"]  = "+tempSum);
				left++;
				right--;
			} else if (tempSum > sum) {
				right--;
			} else {
				left++;
			}
		}
	}

	public static void main(String[] args) {

		int input1[] = {1};
		int input2[] = {1,3,9,2};
		int input3[] = {8,8,12,9,7};
		//System.out.println(subsetSum(input2,5));
		subsetSumPairs(input3, 16);
	}

}