資料結構
網路
關係資料庫管理系統 (RDBMS)
作業系統
Java
MS Excel
iOS
HTML
CSS
Android
Python
C語言程式設計
C++
C#
MongoDB
MySQL
Javascript
PHP
物理學
化學
生物學
數學
英語
經濟學
心理學
社會學
服裝設計
法學C++程式：檢查列表是否可以劃分成k個和相等的子集
假設我們有一個名為nums的數字列表和另一個值k，我們需要檢查是否可以將nums劃分為k個不同的子集，其中每個子集的和相同。
因此，如果輸入類似於nums = [4, 2, 6, 5, 1, 6, 3] k = 3，則輸出為True，因為我們可以將其劃分為：[6, 3]、[6, 2, 1]和[4, 5]。
為了解決這個問題，我們將遵循以下步驟：
- 定義一個函式check()，它將接收一個數組v，
- 初始化i := 1，當i < v的大小，更新（i自增1），執行：
- 如果v[i]不等於v[0]，則：
- 返回false
- 如果v[i]不等於v[0]，則：
- 返回true
- 定義一個函式dfs()，它將接收idx、一個數組nums和一個數組temp，
- 如果idx等於nums的大小，則：
- 返回check(temp)
- ret := false
- 初始化i := 0，當i < temp的大小，更新（i自增1），執行：
- temp[i] := temp[i] + nums[idx]
- ret := dfs(idx + 1, nums, temp)
- 如果ret為true，則：
- 返回true
- temp[i] := temp[i] - nums[idx]
- 返回false
- 在主方法中執行以下操作：
- 定義一個大小為k的陣列temp
- 返回dfs(0, nums, temp)
示例（C++）
讓我們看看下面的實現，以便更好地理解：
#include <bits/stdc++.h>
using namespace std;
class Solution {
public:
bool check(vector<int>& v) {
for (int i = 1; i < v.size(); i++) {
if (v[i] != v[0])
return false;
}
return true;
}
bool dfs(int idx, vector<int>& nums, vector<int>& temp) {
if (idx == nums.size()) {
return check(temp);
}
bool ret = false;
for (int i = 0; i < temp.size(); i++) {
temp[i] += nums[idx];
ret = dfs(idx + 1, nums, temp);
if (ret)
return true;
temp[i] -= nums[idx];
}
return false;
}
bool solve(vector<int>& nums, int k) {
vector<int> temp(k);
return dfs(0, nums, temp);
}
};
bool solve(vector<int>& nums, int k) {
return (new Solution())->solve(nums, k);
}
int main(){
vector<int> v = {4, 2, 6, 5, 1, 6, 3};
int k = 3;
cout << solve(v, 3);
}輸入
{4, 2, 6, 5, 1, 6, 3}, 3輸出
1
更新於：2020年12月12日
瀏覽量：105
廣告