Subsets


Given a set of distinct integers, S, return all possible subsets.
Note:
  • Elements in a subset must be in non-descending order.
  • The solution set must not contain duplicate subsets.
Solution: recursion.

Comments

Post a Comment

Popular posts from this blog

House Robber

You are a professional robber planning to rob houses along a street. Each house has a certain amount of money stashed, the only constraint stopping you from robbing each of them is that adjacent houses have security system connected and it will automatically contact the police if two adjacent houses were broken into on the same night.  Given a list of non-negative integers representing the amount of money of each house, determine the maximum amount of money you can rob tonight without alerting the police. class Solution { public: int rob(vector &num) { if (num.size() < 1) return 0; vector result; result.push_back(num[0]); for (int i = 1; i < num.size(); ++i) { int curr_max = 0; for (int j = 0; j < i - 1; ++j) { curr_max = max(curr_max, num[i] + result[j]); } curr_max = max(curr_max, result[i - 1]); curr_max = max(curr_max, num[i]); result.p...
Read more

[ITint5] Maximum Subarray for a Circular Array

http://www.itint5.com/oj/#8 Classic DP problem, which has also appeared in Leetcode as Maximum subarray . The only difference is, in this problem, empty subarray (where sum is 0) is allowed. So instead of return ret, we could simply return max(0, ret). http://www.itint5.com/oj/#9 Calculate the maximum subarray for a circular array. For example, [1, 3, -2, 6, -1], we should return 9 since 6 + (-1) + 1 + 3 = 9. The following solution might not be optimized. Suppose that the maximum subarray is from A[i] to A[j]. The idea is, consider the following different scenarios: i <= j: it is the same as classic problem. i > j: the sum is A[i : end] + A[start : j]. So we can use two additional arrays: left[j] = maximum subarray, starts from A[start] and ends no later than A[j] right[i] = maximum subarray, starts no earlier than A[i] and ends at A[end] The following code passes the online judge. However, we need O(4n) in time and O(2n) in space. Not sure how to improve this. ...
Read more

Binary Tree Maximum Path Sum

Given a binary tree, find the maximum path sum.   The path may start and end at any node in the tree. Solution: For root node, first check two subtrees and figure out the path with maximum sum in each subtree (and the path must contains the root node). More precisely, we can compare root->val, root->val + leftsubtree, root->val + rightsubtree. But this is not enough since the maximum path might contains two subtrees. We have to compute the value of root->val + leftsubtree + rightsubtree as well. The problem is, we cannot directly return this value since this path cannot go to upper nodes anymore. So we also use another global variable to store the maximum sum in each recursion, and update this variable once we find any path with larger sum. The following code passes the LeetCode Online Large Judge. Thanks for the useful comments.
Read more