4.17.18 課綱

4.17.18 課綱.md

Permutation

1. next_permutation() (sorting!)
2. DFS

class Solution
{
private:
    vector<int> tmp;
    void dfs(vector<int> &nums, bool used[], vector<vector<int>> &ans,
             int depth)
    {
        if ((int)nums.size() == depth) {
            ans.push_back(tmp);
            return;
        }

        for (int i = 0; i < (int)nums.size(); i++) {
            if (used[i] == false) {
                tmp.push_back(nums[i]);
                used[i] = true;
                dfs(nums, used, ans, depth + 1);
                used[i] = false;
                tmp.pop_back();
            }
        }
    }

public:
    vector<vector<int>> permute(vector<int> &nums)
    {
        vector<vector<int>> ans;
        bool used[nums.size()];
        memset(used, false, sizeof(used));
        dfs(nums, used, ans, 0);

        return ans;
    }
};

3. Permutation, no repeat

C(n, k)

for(int i = 0; i < n; i++)
	for(int j = i + 1; j < n; j++) 
		… (k層）

for(int i = 0; i < (1 << n); i++)
	if(__builtin_popcount(i) == k) {
		…
	}

void dfs(int start, int depth) {
	if(depth == k) {
		// ans
		
		return;
	}

	for(int i = start; i < n; i++) {
		dfs(i + 1, depth + 1);
	}
}

dfs(0, k);

Subset

class Solution
{
private:
    vector<int> tmp;
    void dfs(int start, vector<int> &nums, vector<vector<int>> &ans)
    {
        if (start == (int)nums.size())
            return;

        for (int i = start; i < (int)nums.size(); i++) {
            tmp.push_back(nums[i]);
            ans.push_back(tmp);
            dfs(i + 1, nums, ans);
            tmp.pop_back();
        }
    }

public:
    vector<vector<int>> subsets(vector<int> &nums)
    {
        vector<vector<int>> ans;
        ans.push_back(vector<int>()); 
        dfs(0, nums, ans);
        return ans;
    }
};

for(int i = 0; i < (1 << n); i++) {
	全展開
}