Subsets
Bit manipulation and map can be useful aside from backtracking
vector<vector<int>> subsets(vector<int>& nums) {
vector<vector<int>> results(pow(2,nums.size()), vector<int>());
for(int i=1;i<=pow(2,nums.size());i++){
for(int j=0;j<nums.size();j++){
if((((i<<(nums.size()-1-j))&(1<<nums.size()-1))>>(nums.size()-1))==1){
results[i-1].push_back(nums[j]);
}
}
}
return results;
}
Path Sum
Don't suppose that all elements are positive.
Pay attention to problem saying "root to leaf"
Path Sum III
class Solution {
public:
int help(TreeNode* root, int sum, unordered_map<int, int>& store, int pre) {
if (!root) return 0;
root->val += pre;
int res = (root->val == sum) + (store.count(root->val - sum) ? store[root->val - sum] : 0);
store[root->val]++;
res += help(root->left, sum, store, root->val) + help(root->right, sum, store, root->val);
store[root->val]--;
return res;
}
int pathSum(TreeNode* root, int sum) {
unordered_map<int, int> store;
return help(root, sum, store, 0);
}
};
Up-to-bottom is faster and smaller than Bottom-to-Up as no need to store whole sums only need to store current value needed.
Use hashmap to store value makes searching occurrence faster.
