1. StrStr

给定一个 haystack 字符串和一个 needle 字符串，在 haystack 字符串中找出 needle 字符串出现的第一个位置 (从 0 开始)。如果不存在，则返回 -1。

思路：核心点遍历给定字符串字符，判断以当前字符开头字符串是否等于目标字符串

答案代码

int strStr(string haystack, string needle) {
    int n = haystack.size();
    int m = needle.size();

    int j=0;
    for(int i=0;i<=(n-m);i++)
    {
        for(j=0;j<m;j++)
        {
            if(haystack[i+j]!=needle[j])
                break;
        }

        if(j==m)
        {
            return i;
        }
    }

    return -1;
}

2. Subsets

给定一组不含重复元素的整数数组 nums，返回该数组所有可能的子集（幂集）。

思路：这是一个典型的应用回溯法的题目，简单来说就是穷尽所有可能性，算法模板如下

result = []
func backtrack(选择列表,路径):
    if 满足结束条件:
        result.add(路径)
        return
    for 选择 in 选择列表:
        做选择
        backtrack(选择列表,路径)
        撤销选择

答案代码

vector<vector<int>> subsets(vector<int>& nums) {
    // 保存最终结果
    vector<vector<int> > res;
    // 保存中间结果
    vector<int> li;

    backtrack(nums,0,li,res);

    return res;
}

// nums 给定的集合
// pos 下次添加到集合中的元素位置索引
// li 临时结果集合(每次需要复制保存)
// res 最终结果
void backtrack(vector<int>& nums, int pos, vector<int> li,vector<vector<int> >& res)
{
    // 把临时结果保存到最终结果    
    res.push_back(li);

    // 选择、处理结果、再撤销选择
    for(int i=pos;i<nums.size();i++)
    {
        li.push_back(nums[i]);
        backtrack(nums, i+1, li, res);
        li.pop_back();
    }
}