排列与组合

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

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

方法一

方法二

方法三

热门文章

最新文章

相关课程

相关电子书