排列与组合

排列组合是组合学最基本的概念。所谓排列，就是指从给定个数的元素中取出指定个数的元素进行排序。组合则是指从给定个数的元素中仅仅取出指定个数的元素，不考虑排序。

1. 全排列

给定一个 没有重复 数字的序列，返回其所有可能的全排列。

示例:

输入: [1,2,3]

输出:[[1,2,3], [1,3,2], [2,1,3], [2,3,1], [3,1,2], [3,2,1]]

方法一

#include <bits/stdc++.h>
using namespace std;
class Solution
{
public:
    vector<vector<int>> permute(vector<int> &nums)
    {
        vector<vector<int>> res;
        vector<bool> used(nums.size());
        dfs(nums, used, res);
        return res;
    }
private:
    vector<int> stack;
    void dfs(vector<int> &nums, vector<bool> &used, vector<vector<int>> &res)
    {
        if (stack.size() == nums.size())
        {
            res.push_back(stack);
        }
        else
        {
            for (int i = 0; i < nums.size(); i++)
            {
                if (!used[i])
                {
                    used[i] = true;
                    stack.push_back(nums[i]);
                    dfs(nums, used, res);
                    stack.pop_back();
                    used[i] = false;
                }
            }
        }
    }
};
int main()
{
  vector<int> nums = {1,2,3};
  Solution s;
  for (auto res : s.permute(nums)){
    for (auto item : res)
      cout << item << " ";
    cout << endl;
  }
  cout << endl;
  return 0;
}

方法二

#include <bits/stdc++.h>
using namespace std;
class Solution
{
public:
    vector<vector<int>> result;
    vector<vector<int>> permute(vector<int> &nums)
    {
        vector<int> temp(nums.size());
        permutation(nums.size(), 0, nums, temp);
        return result;
    }
    void permutation(int n, int index, vector<int> &nums, vector<int> &temp)
    {
        if (index == n)
        {
            result.push_back(temp);
            return;
        }
        for (int i = 0; i < n; i++)
        {
            bool flag = true;
            for (int j = 0; j <= index - 1; j++)
            {
                if (temp[j] == nums[i])
                    flag = false;
            }
            if (flag)
            {
                temp[index] = nums[i];
                permutation(n, index + 1, nums, temp);
            }
        }
    }
};
int main()
{
  vector<int> nums = {1,2,3};
  Solution s;
  for (auto res : s.permute(nums)){
    for (auto item : res)
      cout << item << " ";
    cout << endl;
  }
  cout << endl;
  return 0;
}

方法三

#include <bits/stdc++.h>
using namespace std;
class Solution
{
public:
    vector<vector<int>> permute(vector<int> &nums)
    {
        vector<vector<int>> res;
        BT(res, nums, 0);
        return res;
    }
    void BT(vector<vector<int>> &res, vector<int> &nums, int start)
    {
        if (start == nums.size())
        {
            res.push_back(nums);
            return;
        }
        else
        {
            for (int i = start; i < nums.size(); i++)
            {
                swap(nums[i], nums[start]);
                BT(res, nums, start + 1);
                swap(nums[i], nums[start]);
            }
        }
    }
};
int main()
{
  vector<int> nums = {1,2,3};
  Solution s;
  for (auto res : s.permute(nums)){
    for (auto item : res)
      cout << item << " ";
    cout << endl;
  }
  cout << endl;
  return 0;
}

2. 全排列 II

给定一个可包含重复数字的序列 nums ，按任意顺序 返回所有不重复的全排列。

示例 1：

输入：nums = [1,1,2]

输出：[[1,1,2], [1,2,1], [2,1,1]]

示例 2：

输入：nums = [1,2,3]

输出：[[1,2,3],[1,3,2],[2,1,3],[2,3,1],[3,1,2],[3,2,1]]

提示：

1 <= nums.length <= 8
-10 <= nums[i] <= 10

方法一

#include <bits/stdc++.h>
using namespace std;
class Solution
{
public:
    vector<vector<int>> permuteUnique(vector<int> &nums)
    {
        vector<vector<int>> res;
        int n = nums.size();
        vector<int> temp;
        vector<bool> visited(n, false);
        sort(nums.begin(), nums.end());
        backtrackpermuteUnique(0, n, nums, temp, res, visited);
        return res;
    }
    void backtrackpermuteUnique(int k, int n, vector<int> nums, vector<int> &temp, vector<vector<int>> &res, vector<bool> &visited)
    {
        if (k == n)
        {
            res.push_back(temp);
            return;
        }
        for (int i = 0; i < n; i++)
        {
            if (!visited[i])
            {
                if (i > 0 && nums[i] == nums[i - 1] && visited[i - 1])
                    continue;
                temp.push_back(nums[i]);
                visited[i] = true;
                backtrackpermuteUnique(k + 1, n, nums, temp, res, visited);
                temp.pop_back();
                visited[i] = false;
            }
        }
    }
};
int main()
{
  vector<int> nums = {1,1,2};
  Solution s;
  for (auto res : s.permuteUnique(nums)){
    for (auto item : res)
      cout << item << " ";
    cout << endl;
  }
  cout << endl;
  return 0;
}

方法二

#include <bits/stdc++.h>
using namespace std;
class Solution
{
public:
    vector<vector<int>> permuteUnique(vector<int> &nums)
    {
        vector<vector<int>> res;
        vector<bool> used(nums.size());
        sort(nums.begin(), nums.end());
        dfs(nums, used, res);
        return res;
    }
private:
    vector<int> stack;
    void dfs(vector<int> &nums, vector<bool> &used, vector<vector<int>> &res)
    {
        if (stack.size() == nums.size())
        {
            res.push_back(stack);
        }
        else
        {
            for (int i = 0; i < nums.size(); i++)
            {
                if (!used[i])
                {
                    if (i > 0 && !used[i - 1] && nums[i - 1] == nums[i])
                    {
                        continue;
                    }
                    stack.push_back(nums[i]);
                    used[i] = true;
                    dfs(nums, used, res);
                    stack.pop_back();
                    used[i] = false;
                }
            }
        }
    }
};
int main()
{
  vector<int> nums = {1,1,2};
  Solution s;
  for (auto res : s.permuteUnique(nums)){
    for (auto item : res)
      cout << item << " ";
    cout << endl;
  }
  cout << endl;
  return 0;
}

3. 组合总和

给定一个无重复元素的数组 candidates 和一个目标数 target ，找出 candidates 中所有可以使数字和为 target 的组合。

candidates 中的数字可以无限制重复被选取。

说明：

所有数字（包括 target）都是正整数。
解集不能包含重复的组合。

示例 1：

输入：candidates = [2,3,6,7], target = 7,

输出：[[7],[2,2,3]]

示例 2：

输入：candidates = [2,3,5], target = 8,

输出：[[2,2,2,2],[2,3,3],[3,5]]

提示：

1 <= candidates.length <= 30

1 <= candidates[i] <= 200

candidate 中的每个元素都是独一无二的。

1 <= target <= 500

方法一

#include <bits/stdc++.h>
using namespace std;
class Solution
{
public:
    void compute(int start, int target, vector<int> &tmp, vector<int> &candidates, vector<vector<int>> &ans)
    {
        int n = candidates.size();
        for (int i = start; i < n; i++)
        {
            if (target > 0)
            {
                tmp.push_back(candidates[i]);
                compute(i, target - candidates[i], tmp, candidates, ans);
                tmp.pop_back();
            }
            else if (target < 0)
                return;
            else
            {
                ans.push_back(tmp);
                return;
            }
        }
    }
    vector<vector<int>> combinationSum(vector<int> &candidates, int target)
    {
        vector<vector<int>> ans;
        vector<int> tmp;
        int v;
        sort(candidates.begin(), candidates.end());
        compute(0, target, tmp, candidates, ans);
        return ans;
    }
};
int main()
{
  vector<int> result, candidates = {2,3,6,7};
  int target = 7;
  Solution s;
  for (auto candidate : s.combinationSum(candidates, target)){
    for (auto item : candidate)
      cout << item << " ";
    cout << endl;
  }
  cout <<endl;
  candidates = {2,3,5};
  target = 8;
  for (auto candidate : s.combinationSum(candidates, target)){
    for (auto item : candidate)
      cout << item << " ";
    cout << endl;
  }
  return 0;
}

方法二

#include <bits/stdc++.h>
using namespace std;
class Solution
{
public:
    vector<vector<int>> combinationSum(vector<int> &candidates, int target)
    {
        vector<vector<int>> res;
        dfs(candidates, 0, target, res);
        return res;
    }
private:
    vector<int> stack;
    void dfs(vector<int> &candidates, int start, int target, vector<vector<int>> &res)
    {
        if (target < 0)
        {
            return;
        }
        else if (target == 0)
        {
            res.push_back(stack);
        }
        else
        {
            for (int i = start; i < candidates.size(); i++)
            {
                stack.push_back(candidates[i]);
                dfs(candidates, i, target - candidates[i], res);
                stack.pop_back();
            }
        }
    }
};
int main()
{
  vector<int> result, candidates = {2,3,6,7};
  int target = 7;
  Solution s;
  for (auto candidate : s.combinationSum(candidates, target)){
    for (auto item : candidate)
      cout << item << " ";
    cout << endl;
  }
  cout <<endl;
  candidates = {2,3,5};
  target = 8;
  for (auto candidate : s.combinationSum(candidates, target)){
    for (auto item : candidate)
      cout << item << " ";
    cout << endl;
  }
  return 0;
}

方法三

#include <bits/stdc++.h>
using namespace std;
class Solution
{
private:
    vector<vector<int>> res;
    vector<int> ans;
public:
    vector<vector<int>> combinationSum(vector<int> &candidates, int target)
    {
        sort(candidates.begin(), candidates.end());
        int left = 0, right = 0;
        for (; right < candidates.size() && candidates[right] <= target; right++)
            ;
        backtrack(candidates, left, right == candidates.size() ? right - 1 : right, target);
        return res;
    }
private:
    void backtrack(vector<int> &candidates, int left, int right, int target)
    {
        if (target < 0)
            return;
        if (!target)
        {
            res.push_back(ans);
            return;
        }
        for (int i = left; i <= right && candidates[i] <= target; i++)
        {
            ans.push_back(candidates[i]);
            backtrack(candidates, i, right, target - candidates[i]);
            ans.pop_back();
        }
    }
};
int main()
{
  vector<int> result, candidates = {2,3,6,7};
  int target = 7;
  Solution s;
  for (auto candidate : s.combinationSum(candidates, target)){
    for (auto item : candidate)
      cout << item << " ";
    cout << endl;
  }
  cout <<endl;
  candidates = {2,3,5};
  target = 8;
  Solution s2;
  for (auto candidate : s2.combinationSum(candidates, target)){
    for (auto item : candidate)
      cout << item << " ";
    cout << endl;
  }
  return 0;
}

4. 组合总和 II

给定一个数组 candidates 和一个目标数 target ，找出 candidates 中所有可以使数字和为 target 的组合。

candidates 中的每个数字在每个组合中只能使用一次。

说明：

所有数字（包括目标数）都是正整数。

解集不能包含重复的组合。

示例 1:

输入: candidates = [10,1,2,7,6,1,5], target = 8,

所求解集为:[[1, 7],[1, 2, 5],[2, 6],[1, 1, 6]]

示例 2:

输入: candidates = [2,5,2,1,2], target = 5,

所求解集为:[[1,2,2],[5]]

方法一

#include <bits/stdc++.h>
using namespace std;
class Solution
{
public:
    vector<vector<int>> combinationSum2(vector<int> &candidates, int target)
    {
        vector<vector<int>> res;
        sort(candidates.begin(), candidates.end());
        dfs(candidates, 0, target, res);
        return res;
    }
private:
    vector<int> stack;
    void dfs(vector<int> &candidates, int start, int target, vector<vector<int>> &res)
    {
        if (target < 0)
        {
            return;
        }
        else if (target == 0)
        {
            res.push_back(stack);
        }
        else
        {
            int last = INT_MIN;
            for (int i = start; i < candidates.size(); i++)
            {
                if (last != candidates[i])
                {
                    stack.push_back(candidates[i]);
                    dfs(candidates, i + 1, target - candidates[i], res);
                    stack.pop_back();
                }
                last = candidates[i];
            }
        }
    }
};
int main()
{
  vector<int> candidates = {10,1,2,7,6,1,5};
  int target = 8;
  Solution s;
  for (auto candidate : s.combinationSum2(candidates, target)){
    for (auto item : candidate)
      cout << item << " ";
    cout << endl;
  }
  cout <<endl;
  candidates = {2,5,2,1,2};
  target = 5;
  for (auto candidate : s.combinationSum2(candidates, target)){
    for (auto item : candidate)
      cout << item << " ";
    cout << endl;
  }
  return 0;
}

方法二

#include <bits/stdc++.h>
using namespace std;
class Solution
{
public:
    void dfs(vector<vector<int>> &ans, vector<int> &candidates, vector<int> &tmp, int target, int start)
    {
        if (target == 0)
        {
            ans.push_back(tmp);
            return;
        }
        else if (target < 0)
        {
            return;
        }
        else
        {
            for (int i = start; i < candidates.size(); i++)
            {
                tmp.push_back(candidates[i]);
                dfs(ans, candidates, tmp, target - candidates[i], i + 1);
                tmp.pop_back();
                while (i + 1 < candidates.size() && candidates[i] == candidates[i + 1])
                    i++;
            }
        }
    }
    vector<vector<int>> combinationSum2(vector<int> &candidates, int target)
    {
        vector<vector<int>> ans;
        vector<int> tmp;
        if (candidates.empty())
            return ans;
        sort(candidates.begin(), candidates.end());
        dfs(ans, candidates, tmp, target, 0);
        return ans;
    }
};
int main()
{
  vector<int> candidates = {10,1,2,7,6,1,5};
  int target = 8;
  Solution s;
  for (auto candidate : s.combinationSum2(candidates, target)){
    for (auto item : candidate)
      cout << item << " ";
    cout << endl;
  }
  cout <<endl;
  candidates = {2,5,2,1,2};
  target = 5;
  for (auto candidate : s.combinationSum2(candidates, target)){
    for (auto item : candidate)
      cout << item << " ";
    cout << endl;
  }
  return 0;
}

方法三

#include <bits/stdc++.h>
using namespace std;
class Solution
{
public:
    vector<vector<int>> combinationSum2(vector<int> &candidates, int target)
    {
        vector<vector<int>> res;
        vector<int> temp;
        backtrace(candidates, temp, 0, target);
        res.assign(m_set.begin(), m_set.end());
        return res;
    }
    void backtrace(vector<int> &candidates,
                   vector<int> &temp,
                   int index,
                   int target)
    {
        if (target == 0)
        {
            sort(temp.begin(), temp.end());
            /* 去重 */
            m_set.insert(temp);
            return;
        }
        /* 设定边界*/
        if (index == candidates.size())
        {
            return;
        }
        if (target >= candidates[index])
        {
            vector<int> tmp(temp);
            tmp.push_back(candidates[index]);
            backtrace(candidates, tmp, index + 1, target - candidates[index]);
        }
        backtrace(candidates, temp, index + 1, target);
    }
private:
    set<vector<int>> m_set;
};
int main()
{
  vector<int> candidates = {10,1,2,7,6,1,5};
  int target = 8;
  Solution s;
  for (auto candidate : s.combinationSum2(candidates, target)){
    for (auto item : candidate)
      cout << item << " ";
    cout << endl;
  }
  cout <<endl;
  candidates = {2,5,2,1,2};
  target = 5;
  Solution s2;
  for (auto candidate : s2.combinationSum2(candidates, target)){
    for (auto item : candidate)
      cout << item << " ";
    cout << endl;
  }
  return 0;
}

C++ leetcode之排列与组合专题

排列与组合

1. 全排列

方法一

方法二

方法三

2. 全排列 II

方法一

方法二

3. 组合总和

方法一

方法二

方法三

4. 组合总和 II

方法一

方法二

方法三

热门文章

最新文章

相关课程

相关电子书

热门

活动广场

任务中心

开发者评测

高校计划

乘风者计划

训练营

阿里云MVP

话题

直播

下载

镜像站

技术资料

插件

C++ leetcode之排列与组合专题

排列与组合

1. 全排列

方法一

方法二

方法三

2. 全排列 II

方法一

方法二

3. 组合总和

方法一

方法二

方法三

4. 组合总和 II

方法一

方法二

方法三

热门文章

最新文章

相关课程

相关电子书