CodingExcercises/SubsetSumProblem.cpp at master · madhu90/CodingExcercises · 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
#include <iostream>
#include <vector>
#include <string>
#include <unordered_map>

// QEUESTION: https://www.techiedelight.com/subset-sum-problem/

class SubsetSum
{
private:
	std::unordered_map<std::string, bool> map;
	const std::vector<int>& arr;
	int targetSum;

public:
	SubsetSum(const std::vector<int>& a, int sum)
		: arr(a), targetSum(sum)
	{

	}

	bool doExponential()
	{
		std::cout << "Exponential approach to subset sum problem" << std::endl;
		return doExponentialHelper(arr.size() - 1, targetSum);
	}

	bool doTopDown()
	{
		std::cout << "Top-down approach to subset sum problem" << std::endl;
		return doTopDownHelper(arr.size() - 1, targetSum);
	}

	bool doBottomUp()
	{
		std::cout << "Bottom-up approach to subset sum problem" << std::endl;
		std::vector<std::vector<bool>> lookup(arr.size() + 1, std::vector<bool>(targetSum + 1, 0));

		// If sum = 0, we have the option of ignoring every element because {} is a subset
		for (int i = 0; i < lookup.size(); ++i)
			lookup[i][0] = true;

		for (int i = 1; i < lookup.size(); ++i) {
			for (int j = 1; j < lookup[i].size(); ++j) {
				if (arr[i - 1] > j)
				{
					lookup[i][j] = lookup[i - 1][j];
				} else {
					lookup[i][j] = lookup[i - 1][j] || lookup[i - 1][j - arr[i - 1]];
				}
			}
		}

		return lookup[arr.size()][targetSum];
	}

private:
	bool doTopDownHelper(int indx, int sum)
	{
		if (sum == 0)
			return true;

		if (indx < 0)
			return false;

		std::string key = std::to_string(indx) + "_" + std::to_string(sum);

		if (map.find(key) == map.end())
		{
			if (sum - arr[indx] >= 0)
			{
				map[key] = doExponentialHelper(indx - 1, sum - arr[indx]) || doExponentialHelper(indx - 1, sum);
			} else {
				map[key] = doExponentialHelper(indx - 1, sum);
			}
		}

		return map[key];
	}

	bool doExponentialHelper(int indx, int sum)
	{
		if (sum == 0)
			return true;

		if (indx < 0)
			return false;

		if (sum - arr[indx] >= 0)
		{
			return doExponentialHelper(indx - 1, sum - arr[indx]) || doExponentialHelper(indx - 1, sum);
		} else {
			return doExponentialHelper(indx - 1, sum);
		}
	}

};

int main()
{
	std::vector<int> arr{ 7, 3, 2, 5, 8 };
	int sum = 14;
	SubsetSum obj(arr, sum);
	bool result1 = obj.doExponential();
	std::cout << "Subset sum result " << result1 << std::endl;
	bool result2 = obj.doTopDown();
	std::cout << "Subset sum result " << result2 << std::endl;
	bool result3 = obj.doBottomUp();
	std::cout << "Subset sum result " << result3 << std::endl;
	return 0;
}