Rule-constrained resource allocation aims to evenly distribute tasks to different processors under the constraints of a set of allocation rules. Conventional heuristic approach fails to achieve optimal solution while simple brute force method has the defects of extremely high computational complexity. To address these limitations, we propose “recursive balanced k-subset sum partition (RBkSP)”, in which iterative “cut-oneout” policy is employed that in each round, only one subset is partitioned whose weights of tasks sum up to 1/𝑘 of the total weight of all tasks in the set. In a single partition, we first create a dynamic programming table with its elements recursively computed, then use “zig-zag search” method to explore the table and find out elements with optimal subset partition, finally assign them to different places. Afterwards, to resolve conflicts during allocation, we use heuristic method which is simple but effective to adjust the allocation of tasks that are contradicted to specific rules. Testing results show RBkSP can achieve more balanced allocation with lower computational complexity over classical benchmarks.