A key prerequisite for planning manipulation together with locomotion of humanoids in complex environments is to find a valid end-pose with a feasible stance location and a full-body configuration that is balanced and collision-free. Prior work based on the inverse dynamic reachability map assumed that the feet are placed next to each other around the stance location on a horizontal plane, and the success rate was correlated with the coverage density of the sampled space, which in turn is limited by the memory required for storing the map. In this letter, we present a framework that uses a paired forward-inverse dynamic reachability map to exploit a greater modularity of the robot’s inherent kinematic structure. The combinatorics of this novel decomposition allows greater coverage in the high-dimensional configuration space while reducing the number of stored samples. This permits drawing samples from a much richer dataset to effectively plan end-poses for both single-handed and bimanual tasks on uneven terrains. This novel method was demonstrated on the 38-DoF NASA Valkyrie humanoid by utilizing and exploiting whole body redundancy for accomplishing manipulation tasks on uneven terrains while avoiding obstacles.