Run Code
|
API
|
Code Wall
|
Users
|
Misc
|
Feedback
|
Login
|
Theme
|
Privacy
|
Patreon
Partition to K Equal Sum Subsets
Language:
Ada
Assembly
Bash
C#
C++ (gcc)
C++ (clang)
C++ (vc++)
C (gcc)
C (clang)
C (vc)
Client Side
Clojure
Common Lisp
D
Elixir
Erlang
F#
Fortran
Go
Haskell
Java
Javascript
Kotlin
Lua
MySql
Node.js
Ocaml
Octave
Objective-C
Oracle
Pascal
Perl
Php
PostgreSQL
Prolog
Python
Python 3
R
Rust
Ruby
Scala
Scheme
Sql Server
Swift
Tcl
Visual Basic
Layout:
Vertical
Horizontal
class Solution { bool foo(int cur, int ind, int cnt, vector<int>& mask, const int n, const int k){ if(cnt > k) return false; if(ind == mask.size()){ if(cnt < k) return false; return (cur == ((1 << n) - 1)); } bool ans = false; // take it if(cur&mask[ind]); else{ ans |= foo(cur|mask[ind], ind + 1, cnt+1, mask, n, k); } if(ans) return true; return foo(cur, ind+1, cnt, mask, n, k); } public: bool canPartitionKSubsets(vector<int>& nums, int K) { int sum = 0, n = nums.size(); for(auto i : nums) sum += i; if((sum % K) != 0) return false; int each = sum / K; vector<int> mask; for(int j = 1; j < (1 << n); j++){ int cur_sum = 0; for(int k = 0; k < n; k ++) if((1<<k)&j) cur_sum += nums[k]; if(cur_sum != each) continue; mask.push_back(j); } // for(auto i : mask) cout << i << " "; cout << endl; return foo(0, 0, 0, mask, n, K); } };
g++
Show compiler warnings
[
+
] Compiler args
[
+
]
Show input
edit mode
|
history
|
discussion