題目：112. Path Sum

連結：https://leetcode.com/problems/path-sum/description/

• 等級：Easy

解題思路

1. 計算路徑總合是否為目標總和，如為總合且無左右子樹，結為正確．

class Solution {  
    public boolean hasPathSum(TreeNode root, int targetSum) {
        if (root == null)
            return false;
        targetSum = targetSum - root.val;
        if (targetSum == 0)
        {
            if (root.left == null && root.right == null)
                return true;
            else
            {
                if(hasPathSum(root.left,targetSum))
                    return true;
                else
                    return hasPathSum(root.right,targetSum);
            }
                
        }
        else
        {
            if(hasPathSum(root.left,targetSum))
                return true;
            else
                return hasPathSum(root.right,targetSum);
        }
    }
}

• Time complexity: O(n)
• Space complexity: O(1)

題目：78. Subsets

連結：https://leetcode.com/problems/subsets/description/

• 等級：Medium

解題思路

class Solution {
    public List<List<Integer>> subsets(int[] nums) {
        List<List<Integer>> rows = new ArrayList<List<Integer>>();
        rows.add(new ArrayList<Integer>());
        for (int i = 0;i < nums.length;i++)
        {
            int n = rows.size();
            for (int j = 0;j < n;j++)
            {
                
                List<Integer> save = new ArrayList(rows.get(j));
                save.add(nums[i]);
                rows.add(save);
            }
        }
        return rows;
    }

• Time complexity: O(n)
• Space complexity: O(1)